[思维]Shortest Path in GCD Graph 2022杭电多校第9场 1008

Problem Description

There is an edge-weighted complete graph KnKn​ with nn vertices, where vertices are labeled through 1,2,...,n1,2,...,n. For each 1≤i

You need to answer qq queries. In each query, given two vertices u,vu,v, you need to answer the length of the shortest path as well as the number of shortest paths between u,vu,v. Since the number of shortest paths may be too large, you only need to output it modulo 998244353998244353.

Input

The first line contains two integers n,q(2≤n≤107,1≤q≤50000)n,q(2≤n≤107,1≤q≤50000), denoting the number vertices in the graph and the number of queries, respectively.

Then qq lines follow, where each line contains two integers u,v(1≤u,v≤n,u≠v)u,v(1≤u,v≤n,u=v), denoting a query between uu and vv.

Output

For each query, output one line contains two integers, denote the length and number of shortest path between given nodes, respectively. Note that only the number of shortest paths should be taken modulo 998244353998244353.

Sample Input

6 2

4 5

3 6

Sample Output

1 1

2 2

题意： 有一个由n个点构成的完全图，两点i，j之间的边权为gcd(i, j)，有q次询问，每次询问给出u，v，求u到v的最短路长度和条数。

分析： 当u和v互质时它们之间最短路一定是1，也就是直接从u走到v，条数也一定是1，当u和v不互指时最短路一定是2，因为可以从u先走到1，再从1走到v，而条数就是和u互质且和v互质的数字个数，不过当u和v的gcd本来就是2时还会多一条直接走过去的路，所以问题就转化为求n以内的和u*v互质的数字个数。先对u和v进行质因数分解，将它们出现过的质因数存下来，然后利用容斥定理可以求出与它俩不互质的数字个数，用n一减就是互质数字个数，不过这道题目时间限制比较紧，对于代码中的各种细节一定要注意优化，比如先筛出质数然后再质因数分解，容斥的时候利用lowbit快速定位1出现的位置，vector进行预分配内存等等。

具体代码如下：

#include 
using namespace std;
 
const int mod = 998244353;
int is_prime[10000005], prime[5000000], cnt, n, q, Log[10000005];
 
int lowbit(int x){
	return x&-x;
}
 
void pre()
{
	for(int i = 2; i <= n; i++)
		is_prime[i] = -1;
	for(int i = 0; i <= 20; i++)
		Log[1<
	for(int i = 2; i <= n; i++){
		if(is_prime[i])
			prime[++cnt] = i;
		for(int j = 1; j <= cnt && i*prime[j] <= n; j++){
			is_prime[i*prime[j]] = 0;
			if(i%prime[j] == 0)
				break;
		}
	}	
}
 
signed main(){
	cin >> n >> q;
	pre();
	for(int i = 1; i <= q; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		if(__gcd(u, v) == 1) puts("1 1");
		else{
			vector<int> p;
			p.reserve(20);
			unordered_map<int, bool> mp;
			int temp = u;
			for(int j = 1; prime[j]*prime[j] <= temp; j++){
				if(temp%prime[j] == 0){
					p.emplace_back(prime[j]);
					mp[prime[j]] = true;
					while(temp%prime[j] == 0)
						temp /= prime[j];
				}
			}
			if(temp != 1){
				p.emplace_back(temp);
				mp[temp] = true;
			}
			temp = v;
			for(int j = 1; prime[j]*prime[j] <= temp; j++){
				if(temp%prime[j] == 0){
					if(!mp[prime[j]])
						p.emplace_back(prime[j]);
					while(temp%prime[j] == 0)
						temp /= prime[j];
				}
			}
			if(temp != 1)
				if(!mp[temp])
					p.emplace_back(temp);
			long long num = 0;
			for(int j = 1; j < 1<size(); j++){
				int neg = 1;
				long long muti = 1;
				int temp = j;
				while(temp){
					neg ^= 1;
					int lb = lowbit(temp);
					muti *= p[Log[lb]];
					temp ^= lb;
					if(muti > n) break;
				}
				if(neg) num -= n/muti;
				else num += n/muti;
			}
			int ans = n-num;
			if(__gcd(u, v) == 2) ans++;
			printf("2 %d\n", ans);
		}
	}
	
	return 0;
}