记录编号	230831	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2820] YY的GCD	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	28.807 s
提交时间	2016-02-24 11:44:01	内存使用	130.01 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int SIZEN=10000010;
typedef long long LL;
bool co[SIZEN];
int mu[SIZEN],pri[SIZEN],cnt=0;
int maxn=0;
LL f[SIZEN];
int N[10010],M[10010];
void prime()
{
	mu[0]=0;
	for(int i=1;i<=maxn;i++) mu[i]=1;
	for(int i=2;i<=maxn;i++)
	{
		if(!co[i])
		{
			pri[++cnt]=i;
			mu[i]=-1;
			for(LL j=2*i;j<=maxn;j+=i)
			{
				co[j]=1;
				if(j%(i*i)==0) mu[j]=0;
				else mu[j]*=(-1);
			}
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		int p=pri[i];
		for(int j=1;j*p<=maxn;j++) f[j*p]+=mu[j];
	}
	f[0]=0;
	for(int i=1;i<=maxn;i++) f[i]+=f[i-1];
}
void calc(int x)
{
	LL ans=0;
	int n,m;
	n=N[x],m=M[x];
	if(n>m) swap(n,m);
	int j=0;
	for(int i=1;i<=n;i=j+1)
	{
		j=min(n/(n/i),m/(m/i));
		ans+=(f[j]-f[i-1])*(n/i)*(m/i);
	}
	printf("%lld\n",ans);
}
int main()
{
	freopen("YYnoGCD.in","r",stdin);
	freopen("YYnoGCD.out","w",stdout);
	int T;
	scanf("%d",&T);
	for(int i=1;i<=T;i++) scanf("%d%d",&N[i],&M[i]),maxn=max(maxn,max(N[i],M[i]));
	prime();
	for(int i=1;i<=T;i++) calc(i);
	return 0;
}