2022杭电多校九 1008-Shortest Path in GCD Graph（质因子+容斥）

题目链接：杭电多校九 - Virtual Judge

题目：

样例输入： 

6 2
4 5
3 6

样例输出：

1 1
2 2

题意：给定n个点的完全图，两个点之间的距离为他们的gcd，q次询问，每次询问给出两个点，问这两个点之间的最短路以及方案数。

分析：不难发现，当询问的两个点u和v互质的时候，最短路一定是1，而且方案数也一定是1，最短路就是两个点之间的直接连边，如果两个点u和v不互质呢？经过思考发现最短路一定不会超过2，由u和v不互质可以得到u和v中任何一个数都不是1，那么从u->1->v长度就是2，所以最短路是不会比2长的，而且不难发现对于任意的x若满足gcd(u,x)=gcd(x,v)=1，那么就有u->x->v长度就是2，但是特别需要注意的一个点就是如果gcd(u,v)=2，那么u和v之间也存在这一条权值为2的直接连边，这也是一个坑点，当时考试的时候还因为这个点wa了好几发。那么问题现在就转变为求解1~n中同时与u和v互质的数的个数，这个我们显然可以用质因子容斥来做，因为对于任意的x如果同时与u和v互斥就等价于不含有u中的质因子，也不含有v中的质因子，那么就等价于1~n中去掉含有u和v的质因子的数，那么这个就可以用容斥来解决了。就是用一个数组同时记录u和v的质因子的去重后结果，然后直接对质因子进行容斥，枚举质因子的出现状态，然后就可以求解。

但是在容斥过程中有三个地方需要额外注意一下，否则容易超时。

（1）我们可以先用欧拉筛求出1~n的所有质数，然后存进prime数组里，在对u和v进行质因子分解时利用事先筛好的素数求解会更快

（2）由于容斥原理的过程是对每一个因数在1~n中出现的次数进行容斥，所以当前容斥的因数如果大于n那么就直接退出循环即可，结果是不会受到影响的。

（3）我们一般容斥枚举出现1的位置是用for循环，但是在考试时发现TLE了，于是可以用lowbit优化一下，我们用lowbit直接返回1的第一次出现的位置，然后再用log求一下位置，然后就会优化很多，剩余操作跟普通容斥相同

细节见代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e7+10,mod=998244353;
int p[N],prime[N],pt;
int log_2[N];
bool vis[N];
int mp[N];
void init()//素数筛 
{
	for(int i=2;i
	{
		if(!vis[i]) prime[++pt]=i;
		for(int j=1;j<=pt&&i*prime[j]
		{
			vis[i*prime[j]]=true;
			if(i%prime[j]==0) break;
		}
	}
}
inline void add(int &x,int y)
{
	if(x+y>mod) x=x+y-mod;
	else x=x+y;
}
inline int lowbit(int x)
{
	return x&-x;
}
int main()
{
	int n,m;
	init();
	for(int i=0;(1<1<//预处理一下以2为底的对数数组 
	cin>>n>>m;
	while(m--)
	{
		int u,v,ans=0;
		scanf("%d%d",&u,&v);
		if(__gcd(u,v)==1)//u。v互质那么直接从u走到v即可
		{
			puts("1 1");
			continue;
		}
		else if(__gcd(u,v)==2) ans+=1;//这个情况需要注意一下，如果gcd(u,v)等于2，需要加上一条从u直接走到v这种情况 
		int tt=0;//tt记录u和v的不同质因子个数 
		for(int i=1;prime[i]*prime[i]<=u;i++)
		{
			if(u%prime[i]==0)
			{
				while(u%prime[i]==0) u/=prime[i];
				if(mp[prime[i]]) continue;
				mp[prime[i]]++;p[++tt]=prime[i];
			}
		}
		if(u>1&&!mp[u])
		{
			p[++tt]=u;
			mp[u]=1;
		}
		for(int i=1;prime[i]*prime[i]<=v;i++)
		{
			if(v%prime[i]==0)
			{
				while(v%prime[i]==0) v/=prime[i];
				if(mp[prime[i]]) continue;
				mp[prime[i]]++;p[++tt]=prime[i];
			}
		}
		if(v>1&&!mp[v])
		{
			p[++tt]=v;
			mp[v]=1;
		}
		for(int i=0;i<1<//容斥求解同时与u和v互质的数的个数 
		{
			int sign=1;
			long long ttt=1;
			int j=i;
			while(j)
			{
				int t=lowbit(j);
				ttt=ttt*p[log_2[t]+1];
				if(ttt>n) break;//当ttt大于n时在1~n内一定没有ttt的倍数，可以剪枝 
				j-=t;
				sign*=-1;
			}
			add(ans,sign*(n/ttt));
		}
		printf("2 %d\n",ans);
		for(int i=1;i<=tt;i++) mp[p[i]]=0;
	}
	return 0;
}