记录编号	37461	评测结果	AAAAAAAAAA
题目名称	最大公约数	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	1.225 s
提交时间	2012-03-30 10:40:14	内存使用	0.35 MiB

#include<stdio.h>

int q,n,m,ans,t,p[10000];

bool flag[50000];

int ou(int k)
{
	int s=k;
	for(int i=1;i<=t&&p[i]*p[i]<=k;i++)
	{
		if(k%p[i]==0)s=s/p[i]*(p[i]-1);
		while(k%p[i]==0)k/=p[i];
	}
	if(k>1)s=s/k*(k-1);
	return s;
}

int main(int argc,char *argv[])
{
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	int i,j;
	for(i=2;i<=32000;i++)if(!flag[i])for(j=i<<1;j<=32000;j+=i)flag[j]=true;
	for(i=2;i<=32000;i++)if(!flag[i])p[++t]=i;
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d%d",&n,&m);
		if(m<2){printf("%d\n",n);continue;}
		ans=0;
		for(i=1;i*i<=n;i++)if(n%i==0)
		{if(i>=m)ans+=ou(n/i);if(i*i!=n&&n/i>=m)ans+=ou(i);}
		printf("%d\n",ans);
	}
	return 0;
}