hdu 2588 搞了良久的数论题 1到n的数与n的公约数大于m的数的个数
hdu 2588 搞了好久的数论题 1到n的数与n的公约数大于m的数的个数
Total Submission(s): 605 Accepted Submission(s): 268
GCD
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 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.
(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
/* 题意: 输入 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; }