首页 > 代码库 > nyoj1007(euler 函数)

nyoj1007(euler 函数)

euler(x)公式能计算小于等于x的并且和x互质的数的个数;

我们再看一下如何求小于等于n的和n互质的数的和, 我们用sum(n)表示;

若gcd(x, a)=1,则有gcd(x, x-a)=1;

证明:假设gcd(x, x-a)=k (k>1),那么有(x-a)%k=0---1式,x%k=0---2式; 由1式和2式可得 a%k=0---3式; 由2式和3式可得gcd(x, a)=k,与gcd(x, a)=1矛盾,即原式得证;

 

由此我们可以得知小于x并且与x互质的数必然是成对出现的并且有对应的一对数和为x;

所以有sum(n)=euler(n)/2*n;

 

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=1007

题意:给出n和m,求满足条件gcd(x, n)>=m的x的x的和,其中1<=x<=n,1<= n, m <= 1e9;

思路:对于任意的x和n,有:x=a*q;

              n=b*q; 

                                     其中q=gcd(x, n),所以gcd(a, b)=1;

所以对于本题,我们可以枚举符合条件的q, 对于每个q对应的b,euler(b)即为所有符合条件的a的数目;

不过本题要求我们求所有符合条件的x的和,sum(b)是所有符合条件的a的和,x=a*q;对于每个符合条件的q对应的x的和,我们用solve(b)表示;

那么solve(b)=q*sum(b),累加所有符合条件的q下的solve(b)即为本题答案;

 

代码:

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 #define mod 1000000007
 4 #define MAXN 100000
 5 using namespace std;
 6 
 7 ll euler(ll x){    
 8     if(x<2){
 9         return 0;
10     }
11     int ans=1;
12     for(int i=2; i*i<=x; i++){
13         if(x%i==0){
14             ans*=i-1;
15             x/=i;
16         }
17         while(x%i==0){
18             x/=i;
19             ans*=i;
20         }
21     }
22     if(x>1){
23         ans*=x-1;
24     }
25     return ans;
26 }
27 
28 ll solve(ll x){
29     if(x==1){
30         return 1;
31     }else{
32         return euler(x)*x/2;
33     }
34 }
35 
36 int main(void){
37     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
38     int t;
39     cin >> t;
40     while(t--){
41         ll n, m, ans=0;
42         cin >> n >> m;
43         for(int i=1; i*i<=n; i++){
44             if(n%i==0){
45                 if(i>=m){
46                     ll cnt=n/i;
47                     ans+=(i*solve(cnt))%mod;
48                 }
49                 if(i*i!=n&&n/i>=m){
50                     ll cnt=i;
51                     ans+=(n/cnt*solve(i))%mod;
52                 }
53             }
54         }
55         cout << (ans%mod+mod)%mod << endl;
56     }
57     return 0;
58 }

 

nyoj1007(euler 函数)