欧拉函数 学习笔记

模板及讲解

定义

定义 $\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$)即可

1
2
3
4
5
6
7
8
9
10
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)$

1
2
3
4
5
6
7
8
9
10
11
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$才行,不相等就必须用莫比乌斯反演

例题1Uva 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)$$

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

1
2
3
4
5
6
7
8
9
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扩展1Luogu 2398

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

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

例题1扩展2Bzoj 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)$$

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

1
2
3
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​$)

常见题型

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