记录编号	372671	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]艾米利亚的施法	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.997 s
提交时间	2017-02-18 20:48:34	内存使用	124.27 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e7+10;
typedef long long ll;
int T,n,m,p[N],cnt;
bool isp[N];ll f[N];
int main()
{
	freopen("aimiliyausemagic.in","r",stdin);
	freopen("aimiliyausemagic.out","w",stdout);
	f[1]=1;
	for (int i=2;i<=1e7;i++){
		if (!isp[i]) p[++cnt]=i,f[i]=i-2;
		for (int j=1;j<=cnt&&i*p[j]<=1e7;j++){
			int P=p[j],x=i*P;
			isp[x]=1;
			if (i%P) f[x]=f[i]*f[P];
			else{
				f[x]=(i/P)%P?f[i/P]*(P-1)*(P-1):f[i]*P;
				break;
			}
		}
	}
	for (int i=2;i<=1e7;i++) f[i]+=f[i-1];
	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+=(f[r]-f[l-1])*(n/l)*(m/l);
		}
		printf("%lld\n",ans);
	}
	return 0;
}