欧拉函数

定义

证明
设N分解质因子的表达式为$N=p_1^{a_1}p_2^{a_2}\dots p_m^{a_m}$ 在1~N中,$p_i$的倍数有$[\frac{N}{pi}]$,这些数与N有相同的质因子，显然不和N互质，同理$p_i p_j$的倍数也不和N互质，我们可以先让N个整数减去所有为$p_1到p_m$的倍数的数，即$N-(N/p_1+N/p_2+\dots N/p_m)$,但是对于一个数，如果既是$p_i$的倍数，又是$p_j$的倍数，那么就会被减去两次，所以需要在加上这些数，即$N-(N/p_1+N/p_2+\dots N/p_m)+ \sum_{1\le i<j\le m}^{}N/(p_ip_j) $,但是如果同时为$p_i,p_j,p_k$的倍数的数又会被多加，需要再减去一次，由容斥原理可以得到
$$ \phi(N)=N(1-\frac{1}{p_1}-\frac{1}{p_2}\dots -\frac{1}{p_n}+\frac{1}{p_1p_2}+\frac{1}{p_1p_3}\dots -\frac{1}{p_1p_2p_3}-\frac{1}{p_2p_2p_4}+(-1)^m\frac{1}{p_1p_2\dots p_m}) $$
观察发现就是上图中所给的式子
代码 时间复杂度$O(\sqrt N)$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
    int a;
    cin>>a;
    int res=a;
    for(int i=2;i<=a/i;i++){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    cout<<res<<endl;
    }
} 

线性筛法求欧拉函数

按照线性筛的方法，从小到大求$\phi(x)$,当质因子枚举到$p_j$,枚举到数字i时，对于一个数$p_ji$,有$$\phi(p_ji) =\begin{cases} p_j\phi(i), & \text{if }i\%p_j=0 \\\ \phi(i)p_j(1-\frac{1}{p_j}), & \text{if }i\%p_j\ne0\end{cases}$$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
int prime[N],cnt;
int eluer[N];
bool st[N];
void get_eluer(int n){
    eluer[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[cnt++]=i,eluer[i]=i-1;
        for(int j=0;prime[j]<=n/i;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0){
                eluer[prime[j]*i]=eluer[i]*prime[j];
                break;
            }
            eluer[prime[j]*i]=eluer[i]*(prime[j]-1);

        }

    }
}
int main()
{
    int n;
    cin>>n;
    get_eluer(n);
    LL res=0;
    for(int i=1;i<=n;i++) res+=eluer[i];
    cout<<res<<endl;
    return 0;
}

欧拉定理

若a和n互质，则
$$ a^{\phi(n)}\equiv 1 \ (mod\ n) $$
证明：
设在1~n范围内，与n互质且两两不相等的数为$b[1],b[2]\dots,b[\phi(n)]$,将每个数乘上a，得到$a\*b[1],a\*b[2]\dots,a\*b[\phi(n)]$,对于任意一个$a\*b[j],1\le j\le \phi(n)$,因为a和$b[j]$都和n互质，所以他们的乘积也和n互质。下面证明一个推论，$（a\*b[j])mod\ n$也和n互质。
设$a*b[j]$模n的余数为t，假设t不和n互质，那么就存在一个正整数d，使得$t=k_1d,n=k_2d$,又因为$t=a\*b[j]-k\*n$,可以得到$a\*b[j]=k\*k_2\*d+k_d$,于是有$a\*b[j]$和n存在一个大于1的公约数d，这与$a\*b[j]$和n互质相矛盾，所以t与n也互质
对于$a\*b[1],a\*b[2]\dots,a\*b[\phi(n)]$,任意两个数模n的余数都不相同，也可以通过反证来证明。因此$a\*b[1],a\*b[2]\dots,a\*b[\phi(n)]$模n的所有余数组成的集合，和$b[1],b[2]\dots,b[\phi(n)]$是相等的，所以有

$$ b[1]b[2]\dots b[\phi(n)]\equiv a^{\phi(n)}b[1]b[2]\dots b[\phi(n)] \\ (mod(n)) \\\ (a^{\phi(n)}-1)b[1]b[2]\dots b[\phi(n)]\equiv 0\\\ a^{\phi(n)}\equiv1 $$
将如果n为质数的话，$\phi(n)=n-1$​,于是就有
$$ a^{n-1}\equiv1\ \ mod(n) \ \text{n为质数} $$
这实际上就是费马小定理