记录编号	355148	评测结果	AAAAAAAAAA
题目名称	最大公约数	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.265 s
提交时间	2016-11-23 21:07:09	内存使用	0.29 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
int calc_phi(int x)
{
    if(x == 1)return 1;
    int a = x;
    int m = sqrt(x+0.5);
    for(int i = 2; i <= m; i++)
    {
        if(!(x%i))a = a/i*(i-1);
        while(!(x%i))x /= i;
    }
    if(x>1) a = a/x*(x-1);
    return a;
}
int main()
{
    freopen("gcd.in", "r", stdin);
    freopen("gcd.out", "w", stdout);
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, z;
        scanf("%d %d", &n, &z);
        long long ans = 0;
        int m = sqrt(n+0.5);
        for(int i = 1; i <= m; i++)
        {
            if(n%i)continue;
            int k = n/i;
            if(k >= z)ans += calc_phi(i);
            if(k != i && i >= z)ans += calc_phi(k);
        }
        printf("%lld\n", ans);
    }
    return 0;
}