欧拉函数 学习笔记

发表于 | 分类于 | | + s

模板及讲解

定义

定义 $\varphi(n)$为$[1,n]$与$n$互质的数的个数。

(1) 给出n的唯一分解式 $n = p^{a1}_1p^{a2}_2p^{a3}_3…p^{ak}_k$ , 求出 $1，2，3…，n$ 中与n互素的数的个数

公式(容斥原理)： $$\varphi(n) = \sum_{S\subseteq(p_1,p_2,…p_k)}(-1)^\left|s\right|\frac {n}{\prod_{p_i\subseteq S}p_i}$$
可变形为：$$\varphi(n) = n(1-\frac1{p_1})(1-\frac1{p_2})…(1-\frac1{p_k})$$
即可在$O(k)$的时间复杂度算出$\varphi(n)$

(2) 不给出唯一分解式求$\varphi(n)$：(Poj 2407)

根据变形的公式，可以枚举所有小于$\sqrt n$的因子，然后之后把他”除干净”(为了提取唯一分解式之中的$p_i$)即可

int phi(int n) {  
    int ans = n;//ans为最后的答案
    int m = (int)sqrt(n + 0.5);
    for (int i = 2; i <= m; i++) if (n % i == 0) {
        ans = ans / i * (i - 1);//ans初值为n，因为1-(1/p) = (p-1)/p，由变形后公式可得
        while (n % i == 0) n /= i;//除干净
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

性质

1、当$n$为质数时，$\varphi (n)=n-1$
2、$\varphi (n)$是积性函数
3、若$n=p^k$，则$\varphi(n)=p^k-p^{k-1}=(p-1)p^{k-1}$
4、
$$n=\sum_{d|n} \varphi(d)$$
5、
$$\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]=\sum_{i=1}^n\sum_{k\mid i,k\mid n}\mu(k)=\sum_{k\mid n}\mu(k)\lfloor\frac nk\rfloor$$
6、$p$为质数，$p,i$不互质，$\varphi(p \cdot i)=\varphi(i) \cdot p$ (线性筛)
7、小于$n$与$n$互质的数和为$\frac{n \cdot \varphi(n)}{2}$

线性筛欧拉函数

复杂度$O(n)$

phi[1] = 1, vis[1] = 1;
for (int i = 2; i <= n; ++i) {
    if (!vis[i]) pri[++tot] = i, phi[i] = i - 1;
    for (int j = 1; j <= tot && (LL)i * (LL)pri[j] <= (LL)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] * phi[pri[j]];
    }
}

运用

$gcd, lcm$相关求和问题

本问题必须$n=m$才行，不相等就必须用莫比乌斯反演。

例题1：Uva 11426
题意：求
$$\sum_{i=1}^n \sum_{j=i+1}^n gcd(i,j)$$

解：

$$\sum_{i=1}^n \sum_{j=i+1}^n gcd(i,j)=\sum_{i=1}^n \sum_{j=1}^{i-1} gcd(i,j)​$$

$$\sum_{d=1} d\sum_{i=1}^n \sum_{j=1}^{i-1} [gcd(i,j)=d]=\sum_{d=1} d\sum_{i=1}^n \sum_{j=1}^{i-1}[gcd(i,j)=1]=\sum_{d=1} d\sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{j=1}^{i-1}[gcd(i,j)=1]=\sum_{d=1} d\sum_{i=1}^{\lfloor \frac nd \rfloor} \varphi(i)$$

设$sum\varphi(k)=\sum_{i=1}^{k} \varphi(i), sumx(k)=\sum_{i=1}^k i$

则答案为

$$\sum_{d=1}^n d \cdot sum\varphi(\lfloor \frac nd \rfloor)$$

线性筛欧拉函数，然后整除分块即可。

while (scanf("%lld", &n) == 1 && n) {
    LL l = 1, r, ans = 0ll;
    while (l <= n) {
         r = n / (n / l);
         ans += sumphi[n / l] * (sumx[r] - sumx[l - 1]);
         l = r + 1; 
    }
    printf("%lld\n", ans);
}

例题1扩展1：Luogu 2398

题意：求
$$\sum_{i=1}^n \sum_{j=1}^n gcd(i,j)$$

解：答案为前面的答案乘二加上$sumx(n)$。
因为相当于对称一个答案，然后加上$gcd(i,i)$的答案。

例题1扩展2：Bzoj 2818

题意：求(其中$p_i​$为素数)
$$\sum_{i=1}^n \sum_{j=1}^n [gcd(i,j)=p_i]$$

先求$j \in [1, i-1]$再对称求解。

$$\sum_{p_k} \sum_{i=1}^n \sum_{j=1}^{i-1} [gcd(i,j)=p_k]=\sum_{p_k} \sum_{i=1}^{\lfloor \frac {n}{p_k} \rfloor} \sum_{j=1}^{i-1} [gcd(i,j)=1]=\sum_{p_k} \sum_{i=1}^{\lfloor \frac {n}{p_k} \rfloor} \varphi(\lfloor \frac {n}{p_k} \rfloor)=\sum_{p_k}sum\varphi(\lfloor \frac {n}{p_k} \rfloor)$$

枚举质数然后直接求即可。

LL ans = 0;
for (LL i = 1; i <= tot; ++i) ans += sumphi[n / pri[i]];
printf("%lld\n", ans * 2 + tot);

总结

  • 一般满足一点，$n=m$，否则要用莫比乌斯反演去求解；
  • 化简这种式子一般要求$j \in [1,i-1]$，方便提公因数后$\varphi$的转化。若要求全部的，加上对称的答案，然后再加上$gcd(i,i)$这样的答案。
  • 类似莫比乌斯反演，最后的式子可以用整除分块去优化；将判断式修改为$[gcd(i,j)=1]​$方便$\varphi​$的出现 (莫比乌斯反演左边不一定是$gcd​$)

常见题型

------ 本文结束 ------