跳转至

欧拉函数

概述

欧拉函数就是对于一个正整数\(n\)，小于\(n\)且和\(n\)互质的正整数(包括1)的个数，记作\(φ(n)\)。

欧拉函数的通式:

\(φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)\)

其中\(p_1, p_2,...,p_n\)为\(n\)的所有质因数，\(n\)是不为\(0\)的整数。\(φ(1)=1\)(唯一和1互质的数就是1本身)。

性质

  • 当\(m,n\)互质时，有\(\phi(m \times n)= \phi(m)* \phi(n)\)；
  • 若\(i%p==0\)，有\(\phi(i \times p) = p \times \phi(i)\)；
  • 对于互质\(x\)与\(p\)，有\(x^{\phi(p)}≡1（mod \ p)\),因此x的逆元为\(x^{\phi(p)-1}\)，即欧拉定理。 （特别地，当p为质数时，\(\phi(p)=p-1\),此时逆元为\(x^{p-2}\)，即费马小定理）
  • 当\(n\)为奇数时，\(\phi(2n)=\phi(n)\)
  • 若\(x\)与\(p\)互质，则\(p-x\)也与\(p\)互质，因此小于\(p\)且与\(p\)互质的数之和为\(\phi(x) \times x/2\);
  • \(N>1\)，不大于\(N\)且和\(N\)互素的所有正整数的和是 \(1/2 \times N \times eular(N)\)。

欧拉筛模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
void eular_()//欧拉筛模板  
{  
    memset(vis,true,sizeof(vis));   
    int cnt=1;  
    vis[1]=false;  
    for(int i=2;i<=N-5;i++)  
    {  
        if(vis[i])  prime[cnt++]=I;
        for(int j=1;j<cnt&&prime[j]*i<=N-5;j++)  
    {  
            vis[prime[j]*i]=false;  
            if(i%prime[j]==0)  
            {  
                break;  
            }  
            //若i为p[j]的倍数，则i=k*p[j]，  
            //在和p[j+1]相乘后得出的x=i*p[j+1]=p[j]*k*p[j+1]  
            //则在i=k*p[j+1]时，由于j从小到大，必定经过之前的p[j]，会重复计算  
        }  
    }  
}

欧拉函数模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int euler(int x)  
{  
    int ans=x;  
    for(int i=2;i*i<=x;i++)//模拟（1-p1）*（1-p2）……过程，pi为x的质因数  
    {  
        if(x%i==0)  
        {  
            ans=ans-ans/i;  
        }  
        while(x%i==0)  
        {  
            x/=i;  
        }  
    }  
    if(x>1) ans=ans-ans/x;//若x不为1，说明仍有一个质因数没有乘  
    return ans;  
}

线性求欧拉函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void euler_()  
{  
    memset(vis,true,sizeof(vis));  
    memset(phi,0,sizeof(phi));  
    int cnt=1;  
    vis[1]=false;  
    phi[1]=1;//特判1,gcd(1,1)=1  
    for(int i=2;i<=N-5;i++)  
    {  
        if(vis[i])  
        {  
            prime[cnt++]=i;  
            phi[i]=i-1;  
        }  
        for(int j=1;j<cnt&&prime[j]*i<=N-5;j++)  
        {  
            vis[prime[j]*i]=false;  
            if(i%prime[j]==0)  
            {  
                phi[prime[j]*i]=phi[i]*prime[j];  
                break;  
            }  
            phi[prime[j]*i]=phi[i]*phi[prime[j]];  
            //若i为p[j]的倍数，则i=k*p[j]，  
            //在和p[j+1]相乘后得出的x=i*p[j+1]=p[j]*k*p[j+1]  
            //则在i=k*p[j+1]时，由于j从小到大，必定经过之前的p[j]，会重复计算  
        }  
    }  
}

例1.HDU2824 The Euler function

题目描述

The Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate (a)+ (a+1)+....+ (b)

输入格式

There are several test cases. Each line has two integers a, b (2<a<b<3000000).

输出格式

Output the result of (a)+ (a+1)+....+ (b)

输入样例 

1
3 100
输出样例 
1
3042

题解

线性求欧拉函数模板题

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 #include<bits/stdc++.h>  
 using namespace std;  
 typedef long long ll;  
 const int N=3e6+10;  
 int phi[N];  
 bool vis[N];  
 int prime[N];  
 int sum[N];  
 void eular_()//欧拉筛模板  
 {  
     memset(vis,true,sizeof(vis));  
     memset(phi,0,sizeof(phi));  
     int cnt=1;  
     vis[1]=false;  
     phi[1]=1;//特判1,gcd(1,1)=1  
     for(int i=2;i<=N-5;i++)  
     {  
         if(vis[i])  
         {  
             prime[cnt++]=i;  
             phi[i]=i-1;  
         }  
         for(int j=1;j<cnt&&prime[j]*i<=N-5;j++)  
         {  
             vis[prime[j]*i]=false;  
             if(i%prime[j]==0)  
             {  
                 phi[prime[j]*i]=phi[i]*prime[j];  
                 break;  
             }  
             phi[prime[j]*i]=phi[i]*phi[prime[j]];  
             //若i为p[j]的倍数，则i=k*p[j]，在和p[j+1]相乘后得出的*p[j+1]=p[j]*k*p[j+1]  
             //则在i=k*p[j+1]时，由于j从小到大，必定经过之前的p[j]，会重复计 
         }  
     }  
 }  
 int main()  
 {  
     int a,b;  
     eular_();  
     while(cin>>a>>b)  
     {  
         ll ans=0;  
        for(int i=a;i<=b;i++) ans+=phi[i];  
        cout<<ans<<endl;  
     }  
     return 0;  
 }

例2.HDU 2588 GCD

题目描述

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.

输入格式

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.

输出格式

For each test case,output the answer on a single line.

输入样例 

1
2
3
4
3
1 1
10 2
10000 72
输出样例 
1
2
3
1
6
260

题解

当\(M\)为\(1\)时，易知答案为\(N\)，当\(M>1\)时，可以确定满足条件的数一定时\(N\)大于\(M\)的约数，如果\(x\)不能整除\(N\)，则\(gcd(x,N)=1<M\)，我们知道\(N\)的约数(设为\(x\))和\(N\)的最大公约数为\(x\)，那是否本题只有N的约数满足条件呢？显然不是，数\(x*k\)(\(k\)为满足条件的某些数)与\(N\)的约数同样为\(x\)，倒推一下，当\(gcd(N，x \times k)=x\)时，有\(gcd(N/x，k)=1\)，即\(k\)满足与\(N/x\)互质时满足\(N\)与\(x \times k\)的最大公约数为\(x\)，于是本题就变成了就\(1-N/x\)内，与\(N/x\)互质的数的个数，用欧拉函数求即可

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
const int N=1e5;  
ll eular(ll x)  
{  
ll ans=x;  
for(int i=2;i*i<=x;i++)  
{  
        if(x%i==0)  
        {  
            ans=ans-ans/i;  
        }  
        while(x%i==0)  
        {  
            x/=i;  
        }  
    }  
    if(x>1) ans=ans-ans/x;  
    return ans;  
}  
int main()  
{  
    int t;  
    cin>>t;  
    while(t--)  
    {  
        ll ans=0;  
        ll n,m;  
        cin>>n>>m;  
        int i;  
        for(i=1;i*i<n;i++)  
        {  
            if(n%i==0)  
            {  
                if(i>=m)  
                {  
                    ans+=eular(n/i);  
                }  
                if(n/i>=m)  
                {  
                    ans+=eular(i);  
                }  
            }  
        }  
        if(i*i==n&&i>=m) ans+=eular(i);  
        cout<<ans<<endl;  
    }  
    return 0;  
}

例3.HDU phi

题目描述

给出若干个正整数n，请你求出最小的m，使得φ(m)≥n。

输入格式

本题有多组输入。

第一行一个正整数T表示数据组数

接下来T行每行一个正整数n

数据保证\(1≤T≤104,1≤n≤106\)。

输出格式

共T行，每行一个数代表对应的答案

输入样例 

1
2
3
4
5
6
5
1
2
3
4
5

输出样例 

1
2
3
4
5
1
3
5
5
7

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
const ll N=5e6+10;  
int phi[N-5];  
bool vis[N-5];  
int prime[N-5];  
struct node  
{  
    int pos;  
    int val;  
    friend bool operator < (const node x,const node y)//对输入进行处优先处理n小的输入并记录  
    {  
        return x.val<y.val;  
    }  
}node[10005];  
int ans[10005];  
int t;  
void euler()  
{  
    int now=1;  
    memset(vis,false,sizeof(vis));  
    memset(phi,0,sizeof(phi));  
    vis[1]=true;  
    phi[1]=1;  
    int cnt=0;  
    for(int i=1;i<=N-10;i++)  
    {  
        if(!vis[i])  
        {  
            prime[++cnt]=i;  
            phi[i]=i-1;  
        }  
        for(int j=1;j<=cnt&&prime[j]*i<=N-10;j++)  
        {  
            vis[prime[j]*i]=true;  
            if(i%prime[j]==0)  
            {  
                phi[i*prime[j]]=phi[i]*prime[j];  
                break;  
            }  
            phi[i*prime[j]]=phi[i]*phi[prime[j]-1];  
        }  
        while(phi[i]>=node[now].val&now<=t)  
        {  
            ans[node[now].pos]=i;  
            now++;  
        }  
        if(now>t) return ;  
    }  
}  
int main()  
{  
    euler();  
    cin>>t;  
    for(int i=1;i<=t;i++)  
    {  
        cin>>node[i].val;  
        node[i].pos=i;  
    }  
    sort(node+1,node+t+1);  
    euler();  
    for(int i=1;i<=t;i++)  
        cout<<ans[i]<<endl;  
    return 0;  
}