hdu 2588 搞了好久的数论题 1到n的数与n的公约数大于m的数的个数

易做图
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 605 Accepted Submission(s): 268

Problem Description
The greatest common divisor 易做图(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

[cpp]
/*
    题意：输入 case个数
    输入n m 表示问从1到n的数与n的公约数大于m的数的个数

思路：
首先找出n的所有大于m的公约数k   然后求出每个对应的n/k的phi(欧拉函数) 即小于n/k的数与n/k互质的个数
那么这些数与n/k互质且小于 n/k   那么这些与n/k互质的数乘以k之后那么就变成了与n公约数为k的数(k>m)
把所有的phi(n/k)相加即是答案当然这思路是参考人家的呜呜。。。。。。。。。。。。。
另外本人有个小疑问：怎么保证这些数没有重复啊比如 k1 k2 均为 n的约数那么如果不同的2个数分别与n/k1 n/k2互质
那么分别乘以k1,k2后为一个数怎么办不是重复了吗？请高手给留个言证明下为什么不会重复
*/
#include<stdio.h>
#include<math.h>
int num[40000],cnt2;
int phi(int x)// 就是公式
{
    int i, res=x;
    for (i = 2; i <(int)sqrt(x * 1.0) + 1; i++)
        if(x%i==0)
        {
            res = res /i * (i - 1);
            while (x % i == 0) x /= i; // 保证i一定是素数
        }
        if (x > 1) res = res /x * (x - 1);//这里小心别溢出了
        return res;
}
int main()
{
    int i,Cas;
    scanf("%d",&Cas);
    while(Cas--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        cnt2=0; int s=0;
        for(i=1;i*i<n;++i)//找出n的所有约数
            if(n%i==0)
            {
            // if(i>=m)
              //   s+=phi(i);
            // if(n/i>=m)
            //   s+=phi(n/i);
                if(i>=m)
                num[cnt2++]=i;
                if(n/i>=m)
                   num[cnt2++]=n/i;
            }
        if(i*i==n&&n%i==0&&i>=m) num[cnt2++]=i;
        for(i=0;i<cnt2;++i)
               s+=phi(n/num[i]);
        printf("%d\n",s);
    }
    return 0;
}

补充：软件开发 , C++ ,