校赛的一道题，出自22年的牛客多校（大概）。

题面

时间限制：C/C++ 2000MS，其他语言 4000MS
内存限制：C/C++ 512MB，其他语言 1024MB

描述

一个带边权的$n$个节点完全图$K_n$，节点标记为$1,2,...,n$。对于每个$1\leq i\lt j\leq n$，$i$节点和$j$节点之间的边$(i,j)$的权值为$gcd(i,j)$，即$i$和$j$的最大公约数。

你需要回答$q$次询问。对于每次询问，给定节点$u,v$，你需要回答$u$和$v$之间的最短路径长度和最短路径数量。由于最短路径数量可能非常大，你只需要输出它模$998244353$的结果。

输入描述

第一行为两个整数$n,q(2 \le n \le 10^7,1 \le q \le 50000)$，分别表示图的节点数和询问数量。
然后有$q$行，每行包含两个整数$u,v(1 \le u,v \le n,u \ne v)$，表示$u$和$v$之间的一次询问。

输出描述

对于每次询问，输出一行两个整数，分别表示给定两个节点之间最短路径的长度和数量。请注意仅最短路径的数量需要模$998244353$。

用例输入 1

6 2
4 5
3 6

用例输出 1

1 1
2 2

解题思路

• 如果$u, v$互质，则最短路径的长度为$1$，最短路径只有两个点之间的连线一条。
• 如果$u, v$不互质，可以找一个与$u, v$都互质的数字如$1$，那最短路径的长度即为$2$，最短路径的数量为$[1 - n]$中与$u,v$互质的正整数的数量；注意如果$gcd(u,v) = 2$，则总数加$1$。
• 在$u,v$不互质的情况中，如果$x$与$u,v$互质，那么$x$和$u,v$的质因数无交集。可以先通过试除法求出$u,v$的质因数，然后在$n$减去所有和$u,v$存在相同质因数的数量，即$n - \sum \frac{n}{质因数} $。可此时会存在重复计算的情况，如$2$和$3$为$u,v$的质因数，$n = 10$，那么此时会减去$\frac{10}{2} + \frac{10}{3} = 8$，其中包含数字$\{2,4,6,8,10,3,6,9\}$，$6$重复算了。所以需要用到容斥定理，如在减去$2,3$的倍数的同时加上$6$的倍数，公式为$$ |A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{i=1}^n |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n| $$

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, q, ans, siz; 
const int N = 1e7;
vector<ll> prime;

void dfs(ll x, ll s, ll o) {
    if(x == siz) {
        ans += o * (n / s); return ;
    }
    dfs(x + 1, s, o);
    if(s <= n / prime[x]) {
        dfs(x + 1, s * prime[x], -o);
    }
} 

void init() {
    ans = 0; prime.clear();
}

void Solve() {
    cin >> n >> q;
    while(q -- ) {
        ll u, v; cin >> u >> v;
        if(__gcd(u, v) == 1) {
            cout << "1 1" << "\n"; continue;
        }
        init();
        ll u1 = u, v1 = v;
        for(ll i = 2; i <= sqrt(u); i ++ ) {
            if(u % i == 0) {
                prime.push_back(i);
                while(u % i == 0) u /= i;
            }
        }
        if(u > 1) {
            prime.push_back(u);
        }
        for(ll i = 2; i <= sqrt(v); i ++ ) {
            if(v % i == 0) {
                if(u1 % i != 0) prime.push_back(i);
                while(v % i == 0) v /= i;
            }
        }
        if(v > 1 && u1 % v != 0) {
            prime.push_back(v);
        }
        siz = prime.size();
        dfs(0, 1, 1);
        if(__gcd(u1, v1) == 2) ans ++ ;
        cout << "2 " << ans << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll T = 1;
//    cin >> T;
    while(T -- ) {
        Solve();
    }
    return 0;
}