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.
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;
}
