GCD HDU - 2588

输入 N 和 M (2<=N<=1000000000, 1<=M<=N),
找出所有满足1<=X<=N 且 gcd(X,N)>=M 的 X 的数量.

Input第一行输入样例数T (T <= 100)
每个样例输入两个整数N , M。 (2<=N<=1000000000, 1<=M<=N)Output对于每组样例，输出一个整数，表示满足条件的X的数量。Sample Input

Sample Output

1

6

260

解析：
　　借鉴uva 11426的思想 但范围太大 用时间换空间 直接求欧拉 再剪枝一下 就好了

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <cctype>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#include <bitset>

#define rap(i, a, n) for(int i=a; i<=n; i++)

#define rep(i, a, n) for(int i=a; i<n; i++)

#define lap(i, a, n) for(int i=n; i>=a; i--)

#define lep(i, a, n) for(int i=n; i>a; i--)

#define rd(a) scanf("%d", &a)

#define rlld(a) scanf("%lld", &a)

#define rc(a) scanf("%c", &a)

#define rs(a) scanf("%s", a)

#define rb(a) scanf("%lf", &a)

#define rf(a) scanf("%f", &a)

#define pd(a) printf("%d\n", a)

#define plld(a) printf("%lld\n", a)

#define pc(a) printf("%c\n", a)

#define ps(a) printf("%s\n", a)

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff;

int g, m;

int ans;

int getphi(int n)

{

    int ret = n;

    for(int i = ; i <= sqrt(n + 0.5); i++)

    {

        if(n % i == )

        {

            ret = ret / i * (i - );

            while(n % i == ) n /= i;

        }

    }

    if(n > )

        ret = ret / n * (n - );

    return ret;

}

int main()

{

    int T;

    rd(T);

    while(T--)

    {

        int sum = ;

        rd(g), rd(m);

        int s = sqrt(g + 0.5);

        for(int i = ; i <= s; i++)

            if(g % i == )

            {

                if(i >= m) sum += getphi(g / i);

                if(g / i >= m) sum += getphi(i);

            }

        if(g !=  && s * s == g && s >= m) sum -= getphi(s);

        pd(sum + );

    }

    return ;

}