数论------欧拉函数

定义：　　

　　F（n）其的值为 x在区间【1，n-1】中满足gcd（x，n）等于1的x的数量（即x与n互质的数目）

求值：

　　先对n'进行唯一分解，取出所有质因数　　F（n）=n*（1-1/P₁）*（1-1/P₂）...... * (1-1/P_n）

唯一分解定理：

　　　任何一个整数n都可以写成 n = P₁^E₁* P₂^E₂... * P_N^{E_{n （其中p为质数，e为指数}}^_）

/*
性质：
        1.假设n为素数，则F(n)=n-1
        2.假设m,n互质，则F(n*m)=F(n)*F(m)     （则也是积性函数的性质，特别重要）
        3.假设n为奇数，则F(2*n)=F(n)        证明很简单，2与n互质，且F(2)=1,即：F(2*n)=F(n)*F(2)=F(n) 
        4.只有F(2)=1,其他F(n)的值都是偶数
        5.一个数的所有质因子之和::(F(n)*n/2) 
        6.a^F(n)%n=1(%n)    (a,n互质)----->欧拉定理
            对于性质6，当n为质数的时候，就变成了费马小定理了    a^n-1%n=1(%n) 

*/

 1 typedef long long ll;
 2 ll euler(int n){
 3     ll ans=1;
 4     for (ll i=2;i*i<=n;i++){
 5         if (n%i==0){     
 6             ans*=(i-1);   //因为欧拉函数也是积性函数 
 7             n/=i;
 8             while (n%i==0){
 9                 n/=i;
10                 ans*=i;
11             }
12         }
13     }
14     if (n>1)    ans*=(n-1);
15     return ans;
16 }

代码实现部分

贴题：

hdu1286（模板题）

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 int eulor(int n){
 5     int sum=1;
 6     for (int i=2;i*i<=n;i++){ 
 7         if (n%i==0){
 8             n/=i;
 9             sum*=(i-1);
10             while (n%i==0){
11                 n/=i;
12                 sum*=i;    
13             }
14         }
15     }
16     if (n>1)    sum*=(n-1);
17     return sum;
18 }
19 int main(){
20     int t;
21     cin>>t;
22     while(t--){
23         int n;
24         cin>>n;
25         cout<<eulor(n)<<endl;
26     }
27     return 0;
28 }

hdu2588

题意：

　　　　题目问的是满足该条件gcd（x，n）>=m，x的取值数目。

　　　　其中题目给定 x取值范围为【1，n-1】，题目给出n和m

解法：

　　　　假设gcd（x，n）=d，显然d是x和n的因数，所以可以看成 gcd（x/d,n/d）=1　　　　然后枚举满足条件的n/d，即可

 1 #include<iostream>
 2 typedef long long ll;
 3 using namespace std;
 4 ll euler(int n){
 5     ll ans=1;
 6     for (ll i=2;i*i<=n;i++){
 7         if (n%i==0){     
 8             ans*=(i-1);   
 9             n/=i;
10             while (n%i==0){
11                 n/=i;
12                 ans*=i;
13             }
14         }
15     }
16     if (n>1)    ans*=(n-1);
17     return ans;
18 }
19 int main(){
20     int t;
21     cin>>t;
22     while (t--){
23         ll n,m,ans=0,i;
24         cin>>n>>m;
25         for (i=1;i*i<=n;i++){
26             if (n%i==0){
27                 if (i>=m)
28                     ans+=euler(n/i);
29                 if (n/i>=m) 
30                     ans+=euler(i);
31             }
32         }
33         if (i>m&&(i-1)*(i-1)==n)    ans-=euler(i-1);
34         cout<<ans<<endl;
35     }
36     
37     return 0;
38 }

上述的是单个欧拉函数值求法，现在介绍类似于线性筛的筛法一次求多组的方法：

hdu2824

 1 #include<iostream>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 const int MAXN=3e6+10;
 6 int pri[MAXN];
 7 void euler(){
 8     pri[1]=1;
 9     for (int i=2;i<MAXN;i++){
10         if (!pri[i]){
11             for (int j=i;j<MAXN;j+=i){
12                 if (!pri[j])    pri[j]=j;
13                 pri[j]=pri[j]/i*(i-1);
14             }
15         }    
16     }
17     return ;
18 } 
19 int main(){
20     euler();
21     int a,b;
22     while (cin>>a>>b){
23         ll ans=0;
24         for (int i=a;i<=b;i++){
25             ans+=pri[i];
26             
27         }
28         cout<<ans<<endl;
29     }
30     return 0;
31 }