杭电多校-Shortest Path in GCD Graph-(二进制容斥+优化)

Shortest Path in GCD Graph

题意：
就是给你n个点，任意两点有条无向边权值是gcd(i,j)。现在m次查询，每次问你a和b的最短距离是多少，这个最短距离的路径有多少个。

思考：

1. 刚开始看到这题思考了下，感觉路径要么是1要么是2，前两天刚做了一个cf题，也是通过中转点走的。那么如果是1的话，那么最短路只有一条，当且仅当a和b互质。当最小路径是2的时候，那么就找找n个点中有多少与a互质并且与b互质的，当然如果gcd(a,b)==2的话这条路径也算。
2. 怎么找有多少与a互质并且与b互质的呢？刚开始我想了想肯定对a和b分解质因数，那么这个数x肯定不能包含a和b的因子，那么我从剩下的因子构造？但是剩下的太多，不好弄。然后又想了想,比如有因子2和5，那么是2的倍数有多少个，是5的倍数有多少个，但是10被减了两次，那么就要加回来，到这里我就想到了，二进制枚举容斥。因为a和b的因子不会太多，最多10个左右。以前做过这两道题：ABC-typewriter，牛客月赛5-无关。都是二进制枚举容斥的做法。
3. 写好但是发现超时了，算了算复杂度3e8左右，2.5秒，很卡常数。对于分解质因数的时候是否第一次出现的时候用数组标记。还有就是二进制枚举的时候，第二维不要直接从0到cnt都枚举，看看这一位是否被选。而是每次拿出来lowbit(x)，直接看看这一位，然后x减去lowbit(x)。同时对sum一直除以va[j+1]，如果sum<=0直接break。当然还有就是可以先乘起来，最后再除以，因为除法比乘法慢很多。
4. 还有一个就是对于每次枚举之后，到底是加还是减。这个要看初始状态，比如这题，初始就假如n个点都符合，那么选1个点的时候就要减去，选两个点的时候加上。所以就是奇数减去偶数加上。 如果是ABC的那道题，那么就是奇数先加上了，这个要具体题目具体分析。牛客月赛那题和本题一样，奇数减去。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e9;
const int N = 2e5+10,M = 1e7+10;

int T,n,m,k;
int va[N],cnt;
int vis[M];
int pre[N];

int bit(int x)
{
	return x&(-x);
}

signed main()
{
	for(int i=0;i<=15;i++) pre[1<<i] = i; //预处理i是2的多少次方，质因子最多15个，所以就处理15次。
	scanf("%d%d",&n,&m);
	while(m--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if(__gcd(a,b)==1)
		{
			printf("1 1\n");
			continue;
		}
		cnt = 0;
		int ans = 0;
		if(__gcd(a,b)==2) ans++;
		for(int i=2;i<=a/i;i++)
		{
			if(a%i==0)
			{
				while(a%i==0) a /= i;
				if(!vis[i])
				{
					vis[i] = 1;
					va[++cnt] = i;
				}
			}
		}
		if(a>1&&!vis[a]) vis[a] = 1,va[++cnt] = a;
		for(int i=2;i<=b/i;i++)
		{
			if(b%i==0)
			{
				while(b%i==0) b /= i;
				if(!vis[i])
				{
					vis[i] = 1;
					va[++cnt] = i;
				}
			}
		}
		if(b>1&&!vis[b]) vis[b] = 1,va[++cnt] = b;
		ans += n;
		for(int i=1;i<(1<<cnt);i++)
		{
			int x = i,res = 0;
			long long sum = 1;
			while(x)
			{
				int t = bit(x);
				x -= t;
				res++;
				sum *= va[pre[t]+1]; //pre[t]是t这个数字是2的多少次方,先乘以最后再除以，因为乘法快很多。
				if(sum>n) break;
			}
			if(res&1) ans -= n/sum;
			else ans += n/sum;
		}
		printf("2 %d\n",ans);
		for(int i=1;i<=cnt;i++) vis[va[i]] = 0;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

总结：
多多思考，多多优化，能优化到多少优化到多少。