欧拉函数学习笔记

定义

$\phi \left(n\right)$φ(n)(读作fai)定义为[1, n]中与n互质的数的个数

显然，当 $n$n 是素数时， $\phi \left(n\right)=n-1$φ(n)=n−1

---

---

---

欧拉函数的求法

关于 $\phi \left(n\right)$φ(n) ，有几种不同的求法，视情况使用。

---

首先呢，我们需要知道一个性质。

两个数 $a,b$a,b 互质时， $\phi \left(ab\right)=\phi \left(a\right)\ast \phi \left(b\right)$φ(ab)=φ(a)∗φ(b)
这是欧拉函数的积性性质，具体证明可以参考网上撒（因为我不会，我们对欧拉函数的求法，基本上都会基于此性质。

---

① 基于质因数分解的求法

考虑 $p，q$p，q都是素数， $n=p\ast q$n=p∗q的情况。
由容斥原理：
$\phi \left(n\right)=n-\frac{n}{p}-\frac{n}{q}+\frac{n}{pq}=n(1-\frac{1}{p})(1-\frac{1}{q})=(p-1)\ast (q-1)=\phi \left(p\right)\ast \phi \left(q\right)$φ(n)=n−pn​−qn​+pqn​=n(1−p1​)(1−q1​)=(p−1)∗(q−1)=φ(p)∗φ(q)
拓展到多个素因子的情况 $n=p_1^{k_1}{p}_2^{k_2}....p_m^{k_m}$n=p1k1​​p2k2​​....pmkm​​
那么
$\phi \left(n\right)=\prod _{i=1}^m\phi \left(p_i\right)=n(1-\frac{1}{p_1})...(1-\frac{1}{p_m})$φ(n)=i=1∏m​φ(pi​)=n(1−p1​1​)...(1−pm​1​)
( 其实把二式拆开，我们会发现满足容斥原理 ）
那么我们就得到了求 $\phi \left(n\right)$φ(n) 的 第一种方法，就是求出 $n$n 的 素因子（俗称质因数分解=。=
复杂度 $O\left(\sqrt{n}\right)$O(n ​)

代码如下：

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

---

② 线性求法

继续考虑
$n=p_1^{k_1}{p}_2^{k_2}....p_m^{k_m}$n=p1k1​​p2k2​​....pmkm​​

Ⅰ $k_1=1$k1​=1

那么 $n/p_1$n/p1​ 与 $p_1$p1​互质，由积性函数可得：
$\phi \left(n\right)=\phi \left(n/p_1\right)\ast \phi \left(p_1\right)=\phi \left(n/p1\right)\ast (p1-1)$φ(n)=φ(n/p1​) ∗ φ(p1​)=φ(n/p1) ∗ (p1−1)

Ⅱ $k_1\>=2$k1​>=2

那么 $n/p_1$n/p1​ 与 $n$n 有共同的素因子，也就是说，与 $n$n 互质的数，同时也与 $n/p1$n/p1 互质。
利用这个性质，我们考虑用 $\phi \left(n/p_1\right)$φ(n/p1​) 来递推。
由 $gcd(a,b)=gcd(a+kb,b)$gcd(a, b)=gcd(a+kb, b)

因此 $\phi \left(n\right)=\phi \left(n/p_1\right)\ast p_1$φ(n)=φ(n/p1​)∗p1​

因此我们先用线性筛求出 $n$n 的最小素因子，然后递推即可。

代码如下

for(i = 2; i <= m; i++){
		if(!x[i]) x[i] = p[++cnt] = i;
		for(j = 1; j <= cnt; j++){
			t = p[j] * i;
			if(t > m) break;
			x[t] = p[j];
			if(i % p[j] == 0) break;
		}
	}
	phi[1] = 1;
	for(i = 2; i <= m; i++){
		if(x[i / x[i]] == x[i]) phi[i] = phi[i / x[i]] * x[i];
		else phi[i] = phi[x / x[i]] * (x[i] - 1);
	} 

---

---

---

欧拉函数的应用

① 将求和问题转化为求个数问题

eg. 求 $s=\sum _{i=1}^n\sum _{j=1}^{n}gcd(i,j)$s=i=1∑n​j=1∑n​gcd(i,j)
考虑枚举 $d=gcd(i,j)$d=gcd(i,j)
那么 $s=\sum _{d=1}^{n}d\ast \sum _{i=1}^n\sum _{j=1}^n\left[gcd\right(i,j)==d]=\sum _{d=1}^{n}d\ast \sum _{i=1}^n\sum _{j=1}^n\left[gcd\right(i/d,j/d)==1]=\sum _{d=1}^{n}d\ast (2\ast \sum _{i=1}^n\sum _{j=1}^i[gcd(i/d,j/d)==1]-1)=\sum _{d=1}^{n}d\ast (2\ast \sum _{i=1}^n\phi (i/d)-1)=\sum _{d=1}^{n}d\ast (2\ast \sum _{i=1}^{n/d}\phi (i)-1)$s=d=1∑n​d∗i=1∑n​j=1∑n​[gcd(i,j)==d]=d=1∑n​d∗i=1∑n​j=1∑n​[gcd(i/d,j/d)==1]=d=1∑n​d∗(2∗i=1∑n​j=1∑i​[gcd(i/d,j/d)==1]−1)=d=1∑n​d∗(2∗i=1∑n​φ(i/d)−1)=d=1∑n​d∗(2∗i=1∑n/d​φ(i)−1)
预处理个前缀和即可。
这种想法非常常见！！！！！很重要！！！

② 欧拉定理及拓展

欧拉定理：如果 $a,n$a,n互质，那么 $a^{\phi \left(n\right)}\equiv 1\left(modn\right)$aφ(n)≡1   (mod n)

证明

构造简化剩余系证明就可以了。

拓展欧拉定理：

$b\>phi\left(n\right)$b>phi(n) 时， $a^b\equiv a^{bmod\phi \left(n\right)+\phi \left(n\right)}\left(modn\right)$ab≡ab mod φ(n)+φ(n)    (mod n)

证明

证明 $a^{\phi \left(n\right)}\equiv a^{2\phi \left(n\right)}\left(modn\right)即可$aφ(n)≡a2φ(n)   (mod n)即可
证明：设 $n=n_1{n}_2$n=n1​n2​,其中 $n1=(a^{\infty },n)$n1=(a∞,n)
则有 $(a,n_2)=(n_1,n_2)=1$(a,n2​)=(n1​,n2​)=1
注意到 $\phi \left(n\right)\ge log2n$φ(n)≥log2n，因此 $n_1\mid a^{\phi \left(n\right)}$n1​∣aφ(n), $a^{\phi \left(n\right)}\equiv a^{2\phi \left(n\right)}\equiv 0\left(mod{n}_1\right)...\left(1\right)$aφ(n)≡a2φ(n)≡0(mod n1​)...(1)
又由 $(n_1,n_2)=1$(n1​,n2​)=1得 $\phi \left(n\right)=\phi \left(n_1\right)\phi \left(n_2\right)$φ(n)=φ(n1​)φ(n2​),
由欧拉定理 $a^{\phi \left(n\right)}\equiv a^{2\phi \left(n\right)}\equiv 1\left(mod{n}_2\right)...\left(2\right)$aφ(n)≡a2φ(n)≡1(mod n2​)...(2)
中国剩余定理合并12两式得证。
推论： $b\>phi\left(n\right)$b>phi(n) 时， $a^b\equiv a^{bmod\phi \left(n\right)+\phi \left(n\right)}\left(modn\right)$ab≡ab mod φ(n)+φ(n)    (mod n)

得到欧拉定理及拓展，我们就可以利用欧拉定理来降幂。

eg.求 $7^{222}mod10$7222 mod 10
分析：(7, 10)=1, 故 $7^{\phi \left(10\right)}=7^5\equiv 1\left(mod10\right)$7φ(10)=75≡1(mod10)
所以 $7^{222}\equiv 7^{222mod5}=7^2=49\equiv 9\left(mod10\right)$7222≡7222 mod 5=72=49≡9(mod10)
即 $7^{222}mod10=9$7222 mod 10=9

---

一些例题

[SDOI2012] Longge的问题 （利用第一条应用

[SDOI2008]沙拉公主的困惑 (利用gcd的性质

bzoj 3884 上帝与集合的正确用法（利用欧拉定理降幂