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

GCDTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 605    Accepted Submission(s): 268


Problem DescriptionInputOutputSample InputSample Output/* 题意： 输入 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;}