记录编号	527542	评测结果	AAAAAAAAAA
题目名称	最大公约数	最终得分	100
用户昵称	HZOI_RXR	是否通过	通过
代码语言	C++	运行时间	0.291 s
提交时间	2019-02-17 10:56:32	内存使用	3.16 MiB

#include<cstdio>
#include<iostream>
using namespace std;
int T,n,m,ans;
int euler(int x)
{
	int res=x;
	for(int i=2;i*i<=x;i++)
	if(x%i==0)
	{
		res=res-res/i;
		do
		x/=i;
		while(x%i==0);
	}
	if(x>1)res=res-res/x;
	return res;
 } 
void work()
{
	ans=0;
	scanf("%d%d",&n,&m);
	if(m==1)
	{
		printf("%d\n",n);
		return;
	}
	
	for(int i=1;i*i<=n;++i)
	{
		if(n%i==0)
		{
			if(i>=m)
			ans+=euler(n/i);
			if(n/i!=i&&(n/i>=m))
			ans+=euler(i);
		}
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	scanf("%d",&T);
	while(T--)work();
}