文章目录

题目链接：

https://www.spoj.com/problems/PGCD/
原来spoj知道题号不行啊。。要知道题的名字才行。。。然后改掉网址后面的题号就阔以了。。。
题意：就是求gcd(x,y)=质数 的个数
做过莫比乌斯的模板的就很清楚，不就是求f(2)+f(3)+f(5)+…+f§么？如果真是这样，那就是一道模板题，就没有什么意思了，果然，暴力这样求T掉了，嗯~不错不错

我们把相同 的F(n)的mu写在一起，就是F(n)*(mu(x1)+mu(x2)+…) 这样，阔以发现，x1,x2…都是n的质因子，然后就用一个Cnt[i]来记录 i 的所以质因子的莫比乌斯函数和，又因为要用到一段一段的，所以就用的是前缀和的那个套路就行了~

打个F的表，前面的系数mu 就不写了

#include"iostream"
#include"cstring"
#include"vector"
typedef long long LL;
using namespace std;
const int maxn=1e7+5;
char mu[maxn];
int Smu[maxn];
vector<int>prime;
bool vis[maxn];
int Cnt[maxn];//Cnt[i]表示i所有因子的mu的和 
int sum[maxn];
void Init(int n)
{
	memset(vis,1,sizeof(vis));
	mu[1]=1;
	Smu[1]=1;
	for(int i=2; i<=n; i++)
	{
		if(vis[i])
		{
			prime.push_back(i);
			mu[i]=-1;
		}
		for(int j=0; j<prime.size()&&i*prime[j]<=n; j++)
		{
			vis[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else mu[i*prime[j]]=-mu[i];
		}
		Smu[i]=Smu[i-1]+mu[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(mu[i]==0)continue;
		for(int j=0;j<prime.size();j++)
		{
			if((LL)i*prime[j]>n)break;
			Cnt[i*prime[j]]+=mu[i]; 
		}
	}
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+Cnt[i];
}
long long F(int d,int n,int m)
{
	return (long long)(n/d)*(m/d);
}
int main()
{
	Init(maxn-5);
	int N,M,T;
	cin>>T;
	while(T--)
	{
		cin>>N>>M;
		LL ans=0;
		int n=min(N,M);
		for(int i=1,j;i<=n;i=j+1)
		{
			j=min(N/(N/i),M/(M/i));
			ans+=1LL*(sum[j]-sum[i-1])*F(i,N,M);
		}
		cout<<ans<<endl;
	}
}