GCD Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2155 Accepted Submission(s): 1093 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 欧拉函数做法： /** 题目：GCD 链接：http://acm.hdu.edu.cn/showproblem.php?pid=2588 题意：给定n，m。求x属于[1,n]。有多少个x满足gcd(x,n)>=m; 思路： x -> [1,n] d = gcd(x,n) >= m d肯定为n的约数。 对一个确定的d = gcd(x,n); 那么：gcd(x/d,n/d) = 1; 满足上面式子的x为：f(n/d); f(y)表示y的欧拉函数。 sigma(f(n/d)) (d为n的约数且d>=m); f(y) = y*(p1-1)/p1*(p2-1)/p2...*(pe-1)/pe; */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> #include<map> #include<set> #include<cmath> #include<queue> #define LL long long using namespace std; typedef long long ll; typedef unsigned long long ull; ll Euler(ll x) { ll n = x; for(int i = 2; i*i<=x; i++){ if(x%i==0){ n = n/i*(i-1); while(x%i==0)x/=i; } } if(x>1){ n = n/x*(x-1); } return n; } vector<int> v; int main() { int T; int n, m; cin>>T; while(T--) { scanf("%d%d",&n,&m); v.clear(); for(int i = 1; i*i<=n; i++){ if(n%i==0){ if(i*i==n){ if(i>=m) v.push_back(i); } else{ if(i>=m) v.push_back(i); if(n/i>=m) v.push_back(n/i); } } } int len = v.size(); int cnt = 0; for(int i = 0; i < len; i++){ cnt += Euler(n/v[i]); } printf("%d ",cnt); } return 0; } 容斥做法： /** 题目：GCD 链接：http://acm.hdu.edu.cn/showproblem.php?pid=2588 题意：给定n，m。求x属于[1,n]。有多少个x满足gcd(x,n)>=m; 思路： 显然d = gcd(x,n)中的d一定是n的约数。 显然d = gcd(d,n); 先获得所有>=m的d; 那么d的倍数为x=k*d，如果小于等于n，则一定也满足gcd(x,n)>=m； k = n/d; 如果对每个d这样计算，会有重复的计算。 当d = 2, 3时候，x=6会多计算一次。 所以要对所有的d进行容斥处理。 问题转化为：n的约数为d，求解d>=m的所有的d在n范围内至少有一个是d的倍数的数有多少个。 */ #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> #include<map> #include<set> #include<cmath> #include<queue> #define LL long long using namespace std; typedef long long ll; typedef unsigned long long ull; vector<int> v; int a[10004], z; ///注意a数组要开大些，约数个数还是不是100就够的。 ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } ll rc(ll n) { ll sum = 0; ll mult; int ones; int len = v.size(); int m = (1<<len); //奇加偶减 for(int i = 1; i < m; i++){ ones = 0; mult = 1; for(int j = 0; j<len; j++){ if(i&(1<<j)){ ones++; mult = mult/gcd(mult,v[j])*v[j]; if(mult>n) break; } } if(ones%2==0){ sum -= n/mult; }else { sum += n/mult; } } return sum; } int main() { int T; int n, m; cin>>T; while(T--) { scanf("%d%d",&n,&m); v.clear(); z = 0; for(int i = 1; i*i<=n; i++){ if(n%i==0){ if(i*i==n){ if(i>=m) a[z++] = i; } else{ if(i>=m) a[z++] = i; if(n/i>=m) a[z++] = n/i; } } } ///出去包含的，比如2,4那么4要去掉。以为4的倍数一定是2的倍数。 sort(a,a+z); for(int i = 0; i < z; i++){ int sign = 0; for(int j = 0; j < i; j++){ if(a[i]%a[j]==0){ sign = 1; break; } } if(sign==0){ v.push_back(a[i]); } } printf("%lld ",rc(n)); } return 0; }