GCD
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
- 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,please answer sum of X satisfies 1<=X<=N and (X,N)>=M.- 输入
- 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 (1<=N<=10^9, 1<=M<=10^9), representing a test case.
- 输出
- Output the answer mod 1000000007
- 样例输入
-
3 1 1 10 2 10000 72
- 样例输出
-
1 35 1305000
- 上传者
- ACM_张书军
题意：Given integers N and M,please answer sum of X satisfies 1<=X<=N and (X,N)>=M./*就在这一句了*/给你两个数 N M 求1~N 之间所有gcdx的和
/*在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。*/ /*思路：枚举n的因子。 假设n的因子为d。d*gcd(x/d,n/d)=1。 d*Euler(n/d)就是因子为gcd(x,n)=d，从而求gcd(x,n)的和。*/ #include<stdio.h> #include<string.h> #include<iostream> using namespace std; const int mod=1000000007; long long Euler(long long n)//欧拉函数 { long long c=n,i; for(i=2; i*i<=n; i++) { if(n%i==0) { while(n%i==0) n/=i; c=c/i*(i-1);//φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn); } } if(n!=1) c=c/n*(n-1); return c; } //求 x和 long long Euler_sum(long long n) { if(n==1) return 1; else return n*Euler(n)/2; } int main() { long long a,b; int t; cin>>t; while(t--) { while(cin>>a>>b) { int cnt; long long i,c=0; for(i=1; i*i<=a; i++) { if(a%i==0) { if(i>=b) { cnt=i;//- - c=(c+cnt*Euler_sum(a/cnt))%mod; } if(i*i!=a&&a/i>=b)//枚举i与n的因子。 { cnt=a/i; c=(c+cnt*Euler_sum(a/cnt))%mod; } } } cout<<c<<endl; } } }