欧拉函数与欧拉反演

欧拉函数

定义 $\varphi(n)$ 表示 $1\sim n$ 中与 $n$ 互质的数个数。
形式化地讲， $\varphi(n)=\sum_{i=1}^{x}[\gcd(i,n)=1]$ ，其中 $[\cdot]$ 表示艾佛森括号。

性质 1

$\varphi(p^k)=p^k-p^{k-1}$ ，其中 $p$ 为质数。

证明：
$1\sim p^k$ 中恰有 $p^{k-1}$ 个 $p$ 的倍数，只有他们与 $p^k$ 不互质。
即 $\varphi(p^k)=p^k-p^{k-1}$ 。

性质 2

欧拉函数是积性函数。
也就是说，对于互质 $a,b$ ， $\varphi(ab)=\varphi(a)\varphi(b)$ 。

证明：
引理1： $x$ 与 $ab$ 互质的充要条件是 $x$ 与 $a$ 互质且 $x$ 与 $b$ 互质。
证明：显然。

引理2： $x$ 与 $a$ 互质的充要条件是 $x \bmod a$ 与 $a$ 互质。
证明：由辗转相除法可知， $\gcd(x,a)=\gcd(x \bmod a,a)$ ，而互质即两数最大公约数为 $1$ ，故成立。

引理3：若 $a,b$ 互质， $k,k+a,k+2a,\ldots,k+(b-1)a$ 在模 $b$ 意义下遍历 $0\sim b-1$ 。
证明：只需证这 $b$ 个数模 $b$ 互不相同即可。假设存在两个数相同，即 $\exist k<b, ka\equiv 0\pmod b$ ，这显然与 $a,b$ 互质矛盾，故原命题成立。

则把 $1\sim ab$ 写成一个 $a$ 列 $b$ 行的表格。

$\begin{matrix} 1 &2 &\ldots & a\\ (a+1)& (a+2) & \ldots &2a \\ \vdots & \vdots & \ddots & \vdots\\ (b-1)a+1 & (b-1)a+2& \ldots & ab \end{matrix}$

观察每一行，发现模 $a$ 都为 $0\sim a-1$ ，则根据引理 2，恰有 $\varphi(a)$ 列与 $a$ 互质。
观察每一列，每一列为 $k,k+a,k+2a,\ldots,k+(b-1)a$ 。根据引理 3，所以这 $b$ 个数恰好不重复的遍历了 $0\sim b-1$ ，故每列中恰有 $\varphi(b)$ 个与 $b$ 互质。
由引理 1 可得， $\varphi(ab)=\varphi(a)\varphi(b)$ 。

性质3

设 $n$ 的唯一分解 $n = \displaystyle\prod_{i=1}^s p_i^{\alpha_i}$ ，则 $\varphi(n)=n\displaystyle\prod_{i=1}^s\dfrac{p_i-1}{p_i}$ 。

证明：
通过性质1，2推导可得。

$\begin{aligned} &\varphi(n)\\ & = \displaystyle\prod_{i = 1}^s\varphi(p_i^{\alpha_i})\\ & = \displaystyle\prod_{i = 1}^s p_i^{\alpha_i-1}(1-p_i)\\ &=n\displaystyle\prod_{i=1}^s\dfrac{p_i-1}{p_i} \end{aligned}$

应用： $O(\sqrt n)$ 求一个数的欧拉函数。

template<typename T>
T phi(T x){
    T ans = x;
    for(T i=2;i*i<=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;
}

性质4

$\varphi(np)=\begin{cases} \varphi(n)\cdot(p-1) & p\nmid n \\ \varphi(n)\cdot p & p\mid n \end{cases}$

证明：
通过性质 3 可以很简单证明，留作读者练习。

应用： $O(n)$ 求出 $1\sim n$ 的欧拉函数值（线性筛）。

int p[N/2],cnt,phi[N];
bool vis[N];

void init(){
    vis[1]=1;phi[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i]){
            p[++cnt]=i;
            phi[i]=i-1; // 质数
        }
        for(int j=1;j<=cnt&&i*p[j]<N;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            else phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
}

性质5（欧拉反演）

$n = \displaystyle\sum_{d\mid n} \varphi(d)$ 。

证明：
考虑枚举 $1\sim n$ 中和 $n$ 的最大公约数为 $d$ 的数个数。

$\begin{aligned} n=& \displaystyle\sum_{d\mid n}\sum_{i=1}^n[\gcd(i,n)=d]\\ =& \displaystyle\sum_{d\mid n}\sum_{i=1}^{ n/d}[\gcd(i, n/d)=1]\\ =& \displaystyle\sum_{d\mid n}\varphi(d)\\ \end{aligned}$

欧拉反演

通过运用 $n = \displaystyle\sum_{d\mid n} \varphi(d)$ ，我们可以解决一系列问题，一种典型题目是求一系列 $\gcd$ 的和。（对比莫比乌斯反演，莫反求的是 $\gcd=k$ 的数量）

GCD SUM

P2398 GCD SUM
求 $\displaystyle\sum_{i=1}^n \displaystyle\sum_{j=1}^n \gcd(i,j)$ 。

$\begin{aligned} &\displaystyle\sum_{i=1}^n \displaystyle\sum_{j=1}^n \gcd(i,j)\\ =&\displaystyle\sum_{i=1}^n \displaystyle\sum_{j=1}^n \displaystyle\sum_{d\mid \gcd(i,j)} \varphi(d)\\ =&\displaystyle\sum_{i=1}^n \displaystyle\sum_{j=1}^n \displaystyle\sum_{d}[d\mid i][d\mid j] \varphi(d)\\ =&\displaystyle\sum_{d=1}^n \sum_{d\mid i}\sum_{d\mid j} \varphi(d)\\ =&\displaystyle\sum_{d=1}^n \left \lfloor \dfrac{n}{d} \right \rfloor^2 \varphi(d)\\ \end{aligned}$

练习：P1390 公约数的和

求 n 个数两两最大公约数的和

求 $\displaystyle\sum_{i=1}^n \displaystyle\sum_{j=1}^{i-1} \gcd(a_i,a_j)$ 。

只考虑一个 $i$ 求出 $\displaystyle\sum_{j=1}^{i-1} \gcd(a_i,a_j)$ 。

$\begin{aligned} & \displaystyle\sum_{j=1}^{i-1} \gcd(a_i,a_j)\\ =& \displaystyle\sum_{j=1}^{i-1} \sum_{d\mid \gcd(a_i,a_j)}\varphi(d)\\ =& \sum_{d\mid a_i}\varphi(d)\displaystyle\sum_{j=1}^{i-1}[d\mid j]\\ \end{aligned}$