记录编号	549868	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2820] YY的GCD	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	9.495 s
提交时间	2020-02-25 18:51:28	内存使用	166.25 MiB

#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<time.h> 
using namespace std;
int vis[10000001],F[10000001],miu[10000001],pri[10000001],cnt,t,n,m;
void INIT()
{
	miu[1]=1;
	for(int i=2;i<=10000000;i++)
	{
		if(!vis[i])
		{
			pri[++cnt]=i;
			miu[i]=-1;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(pri[j]*i>10000000)
				break;
			vis[pri[j]*i]=1;
			if(i%pri[j]==0)
			{
				break;
			}
			miu[pri[j]*i]=-miu[i];
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		for(int j=1;j*pri[i]<=10000000;j++)
		{
			F[j*pri[i]]+=miu[j];
		}
	}
	for(int i=1;i<=10000000;i++)
	{
		F[i]+=F[i-1];
	}
}
long long Solve()
{
	long long ans=0;
	for(int l=1,r;l<=min(n,m);l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		ans+=(long long)(F[r]-F[l-1])*(n/l)*(m/l);
	}
	return ans;
}
signed main()
{
	freopen("YYnoGCD.in","r",stdin);
	freopen("YYnoGCD.out","w",stdout);
	scanf("%d",&t);
	INIT();
	while(t--)
	{
		scanf("%d%d",&n,&m);
		printf("%lld\n",Solve());
	}
	return 0;
}