数论学习笔记（欧拉函数）

ccxXF · 2026-08-21 20:58:54 · 算法·理论

前言

好久之前学的欧拉函数，现在都快忘光了，写篇笔记加深一下记忆。

前置知识——费马小定理

费马小定理及其应用

逆元：

欧拉函数的定义和一些性质

定义

欧拉函数，定义为从 1 到 n 中于 n 互质的数字的个数，记为 \varphi(n)。

性质

1. 欧拉函数为积性函数，即：

   \varphi(nm)=\varphi(n)\varphi(m)\;(\gcd(n,m)=1)

   证明如下：

   假设数字 n 和数字 m 互质，则和 mn 互质等价于同时和 n 互质和 m 互质，假设一个小于等于 mn 数字 t 与 n 和 m 的余数数对为 (i,j)，下面证明对于每一个余数数对 (i,j)，其对应的数值 t 是唯一且确定的。

   考虑反证法，假设存在两个数字 l 和 r 的余数数对都是 (i,j)，下面统一 1 \le l < r \le mn，则 r-l 能被 n 和 m 整除，也就是被 mn 整除，但是有定义可得 1\le r-l <mn，即不存在一个数字和 mn 整除，所以假设不成立。

   因此，和 mn 互质的个数就是和 n 互质的个数与和 m 互质的个数，即 \varphi(mn)=\varphi(n)\varphi(m)\;(\gcd(n,m)=1)。

2. 当 n 为质数时，\varphi(n)=n-1，这很显然，因为一个质数 n 与从 1 到 n-1 中的数都互质。

3. \varphi(p^{k})=(p-1)p^{k-1}\;(\text{p is prime})

   证明如下：

   \begin{aligned} \varphi(p^k) &= p^k - \sum_{i=1}^p [\gcd(p^k, i) \neq 1] \\ &= p^k - \sum_{i=1}^p [p \mid i] \\ &= p^k - p^{k-1} \\ &= (p-1)p^{k-1} \end{aligned}

4. 对于任意一个 n，设

   n=\prod_{i=1}^{m}{a_i}^{p_i}

   则有

   \varphi(n)=n\prod_{i=1}^{m}(1-\frac{1}{a_i})

   证明如下：

   \begin{aligned} \varphi(n)&=\varphi(\prod_{i=1}^{m}{a_i}^{p_i})\\ &=\prod_{i=1}^{m}\varphi({a_i}^{p_i})\\ &=\prod_{i=1}^{m}(a_i-1){a_i}^{p_i-1}\\ &=\prod_{i=1}^{m}{a_i}^{p_i}(\frac{a_i-1}{a_i})\\ &=\prod_{i=1}^{m}{a_i}^{p_i}\times\prod_{i=1}^{m}(1-\frac{1}{a_i})\\ &=n\prod_{i=1}^{m}(1-\frac{1}{a_i}) \end{aligned}

5. 对于任意一个 n，都有

   n=\sum_{d|n}\varphi(d)

   证明如下：

   给出 n 个分数 \frac{1}{n},\frac{2}{n},\dots,\frac{n}{n}，将这些分数约分后，我们定义一个函数 f(i) 代表以 i 为分母且与分子互质的分子小于等于分母的分数的数量，那么很显然 n=\sum_{d|n}f(d)，这个函数 f(i) 的定义与欧拉函数的定义一样，所以该式子就为 n=\sum_{d|n}\varphi(d)。

   如何求欧拉函数？

   质因数分解求欧拉函数

   我们根据性质 4 可以得出，\varphi(n)=n\prod_{i=1}^{m}(1-\frac{1}{a_i})，我们只需按这个模拟即可，时间复杂度为 O(\sqrt n)。

   Code

   int phi(int x){
    int ans=x;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0)ans=ans/i*(i-1);
        while(x%i==0)x/=i;
    }
    if(x>1)ans=ans/x*(x-1);
    return ans;
   }

   线性筛求欧拉函数

   上面的求解方法适合在只需要求解少量的欧拉函数的值，当需要求从 1 到 n 中的所有的欧拉函数的值时，就可以用到线性筛求解时间复杂度为 O(n) 。

先说结论，对于一个质数 p，如果 p \nmid i，则 \varphi(pi)=(p-1)\varphi(i)，如果 p \mid i，则 \varphi(pi)=p\varphi(i)。下面给出证明。

对于第一种 p \nmid i 的情况，根据性质 1 可得 \varphi(pi)=\varphi(p)\varphi(i)，又因为 p 为质数，所以根据性质 2，\varphi(pi)=(p-1)\varphi(i)。

对于第二种 p \mid i 的情况，由于 i 中一定有至少一个因数 p，所以我们不妨设 i=p^km，其中 k\ge1，这样 m 中没有因数 p，所以 m 和 p^k 互质，所以 \varphi(i)=\varphi(p^k)\varphi(m)=(p-1)p^{k-1}\varphi(m)，同理可得 \varphi(pi)=\varphi(p^{k+1}m)=\varphi(p^{k+1})\varphi(m)，根据性质 3，又得：

我们惊奇的发现后面的 (p-1)p^{k-1}\varphi(m) 就是之前定义的 \varphi(i)，所以 \varphi(pi)=p\varphi(i)，得证。

Code

const int N=1e7+10;
bool f[N];
int phi[N];
vector<int>prime;
void get_phi(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!f[i])prime.push_back(i),phi[i]=i-1;
        for(int j=0;j<prime.size()&&prime[j]*i<=n;j++){
            f[prime[j]*i]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

欧拉定理

与费马小定理的证明类似，下面给出证明。

证明：

将所有的和 n 互质的数提出来，构成一个数列，即 r_1,r_2,\dots,r_{\varphi(n)}，那么很显然这些数字都两两不同余。有一个性质，即同时乘上一个数字 a 且 \gcd(a,n)=1，那么 ar_1,ar_2,\dots,ar_{\varphi(n)} 这个序列中的每一个数字都和 n 互质且两两不同余，下面证明。

对于序列中的每一个数字都和 n 互质，由于 \gcd(a,n)=1 且 \gcd(r_i,n)=1，所以 \gcd(ar_i,n)=1。

对于序列中的每一个数字两两不同余，我们考虑反证法。若存在一对数 ar_i\equiv ar_j\pmod n，那么肯定有 r_i\equiv r_j\pmod n，和定义矛盾，故每一个数字两两不同余。

有了这个性质，就说明将 ar_1,ar_2,\dots,ar_{\varphi(n)} 中的每一个数字模 n 与 r_1,r_2,\dots,r_{\varphi(n)} 是相同的，因为新序列中的数字都和 n 互质，且两两不同余，与原序列的定义是一样的。

下面，我们把 ar_1,ar_2,\dots,ar_{\varphi(n)} 和 r_1,r_2,\dots,r_{\varphi(n)} 中的每一个数字乘起来，即 (ar_1)(ar_2)\dots(ar_{\varphi(n)}) 和 r_1r_2\dots r_{\varphi(n)}，很显然这两个乘积模 n 是同余的，即：

也就是：

由于两边都有 r_1r_2\dots r_{\varphi(n)}，所以可得：

扩展欧拉定理

这个定理就不需要 \gcd(a,m)=1 了，该定理为：

笔者太蒟蒻了不会证，感兴趣的读者可以去了解一下，个人认为只需要记 a^p \equiv a^{p \bmod \varphi(m)+\varphi(m)} \pmod m 就行了。

经典套路

给出一个 n，求出 \sum_{i-1}^{n}\sum_{j-1}^{n}\gcd(i,j) 的值。

根据性质 5 可将这个式子化成：

有一个套路就是将 \sum_{d|n}\varphi(d) 提到前面去，并考虑每一个 d 对这个式子的贡献，于是这个问题就转化成了：给你一个数字 d，求出有几对(i,j) 满足 i 和 j 都是 d 的倍数，很显然，有 \left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor 对，于是该式子就转化成了：

可在 O(\min(n,m)) 的时间复杂度之内完成。

像这样的有 \gcd 的式子，一般可以将这个式子改成 \sum_{d|n}\varphi(d) 并将其移到前面进行求解。

例题

题目大意

P2158 [SDOI2008] 仪仗队

题目分析

观察可发现，能被看到的人一定是 \gcd(x,y)=1，因为若不是的话，(x,y) 会被 (\frac{x}{\gcd(x,y)},\frac{y}{\gcd(x,y)}) 这个人挡住。

于是这道题目可以化简成如下式子：

我们固定一个前面 i，发现后面的一串正好就是 \varphi(i)，直接求和即可，但是这只限于 j \le i 的情况，所以要乘 2，又但是 i=1 的情况被计算了 2 次，所以将去一个 \varphi(1)，也就是 1，所以最终答案为：

使用线性筛求解，时间复杂度为 O(n)。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define speed ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define pb push_back
const int N=4e4+10;
int n,pri[N],cnt;
int phi[N],ans;
bitset<N>vis;
void init(){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i])pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;i*pri[j]<=n;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            else phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
}
signed main(){
    speed
    cin>>n;
    if(n==1)return cout<<0,0;
    init();
    for(int i=1;i<n;i++)ans+=phi[i];
    cout<<2*ans+1;
    return 0;
}

题目大意

P1390 公约数的和

题目分析

让我们求：

将 d 移到前面，这个式子就变成了，从 1 到 n 中的所有的 d 的倍数中，选出两个数字有多少种方案，但是这题要求 i<j，所以最后要除以 2，该式子就变成了：

直接线性筛求解即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define speed ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define debug cout<<"\n-----------debug-----------\n";
const int N=2e6+10;
int n,phi[N],ans;
bool f[N];
vector<int>prime;
void init(){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!f[i])prime.push_back(i),phi[i]=i-1;
        for(int j=0;j<prime.size()&&prime[j]*i<=n;j++){
            f[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            else phi[i*prime[j]]=(prime[j]-1)*phi[i];
        }
    }
}
signed main(){
    speed
    cin>>n;
    init();
    for(int i=1;i<=n;i++){
        ans+=phi[i]*(n/i)*(n/i-1)/2;
    }
    cout<<ans;
    return 0;
}

后记

这篇文章写的有些匆忙，如果有地方写错了，欢迎各位大佬指出。