博客

互质问题，特别注意1的处理！！！

构建了容斥和莫比乌斯函数的对应关系

详见zyf2000的博客

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
const int N=200005;

int n,q,vis[N];
vector<int> p[N];
ll f[500005];

bool b[500005];int pri[500005],num,mi[500005],u[500005];
void init()
{
	u[1]=1;
	for (int i=2;i<=500000;i++)
	{
		if (!b[i]) pri[++num]=i,mi[i]=i,u[i]=-1;
		for (int j=1;j<=num&&i*pri[j]<=500000;j++) 
		{
			b[i*pri[j]]=true;mi[i*pri[j]]=pri[j];
			if (i%pri[j]==0) u[i*pri[j]]=0;else u[i*pri[j]]=-u[i];
			if (i%pri[j]==0) break;
		}
	}
}

ll work(int x)
{
	if (p[x].size()==0) return f[1]-1;
	int sz=p[x].size();
	int S=1<<sz,tmp;ll ans=