题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2588
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6.
(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem:
Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.

Input

The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.

Output

For each test case,output the answer on a single line.

Sample Input

3
1 1
10 2
10000 72

Sample Output

1
6
260

Problem solving report:

Description: 输入n ,m。判断满足gcd(x,n)>=m条件x的个数。
Problem solving: 因为gcd(x,n)>=m，所以可以令gcd(x,n)=y,1<=x<=n,y>=m -> gcd(x/y,n/y)=1;
因为x<=n，所以x/y<=n/y，所以我们可以枚举y，利用欧拉函数打表，求出y的方案数phi(n/y)，并可同时求出n/y的方案数phi(y)。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
int Euler(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; i++) {
        if (!(n % i)) {
            ans = ans / i * (i - 1);
            while (!(n % i))
                n /= i;
        }
    }
    if (n != 1)
        ans = ans / n * (n - 1);
    return ans;
}
int main() {
    int t, n, m, ans;
    scanf("%d", &t);
    while (t--) {
        ans = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i * i <= n; i++) {
            if (!(n % i)) {
                if (i >= m)
                    ans += Euler(n / i);
                if (n / i >= m && i * i != n)
                    ans += Euler(i);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}