记录编号	374102	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2820] YY的GCD	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	11.166 s
提交时间	2017-02-22 13:46:21	内存使用	162.41 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e7+10;
int T,n,m,u[N],p[N],cnt;
ll s[N];bool isp[N];
void init(){
	n=1e7;u[1]=1;
	for (int i=2;i<=n;i++){
		if (!isp[i]) p[++cnt]=i,u[i]=-1,s[i]=1;
		for (int j=1;j<=cnt&&i*p[j]<=n;j++){
			int x=i*p[j];
			isp[x]=1;
			if (!(i%p[j])){
				u[x]=0;
				s[x]=u[i];
				break;
			}
			u[x]=-u[i];
			s[x]=u[i]-s[i];
		}
	}
	for (int i=1;i<=n;i++) s[i]+=s[i-1];
}
int main()
{
	freopen("YYnoGCD.in","r",stdin);
	freopen("YYnoGCD.out","w",stdout);
	init();
	scanf("%d",&T);
	while (T--){
		scanf("%d%d",&n,&m);
		if (n>m) swap(n,m);
		ll ans=0;
		for (int l=1,r;l<=n;l=r+1){
			r=min(n/(n/l),m/(m/l));
			ans+=(s[r]-s[l-1])*(n/l)*(m/l);
		}
		printf("%lld\n",ans);
	}
	return 0;
}