记录编号	389775	评测结果	AAAAAAAAAA
题目名称	[SDOI 2015] 约数个数和	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.747 s
提交时间	2017-03-31 21:01:03	内存使用	1.10 MiB

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