16 KiB
欧拉函数专题
一、定义
定义：欧拉函数是小于n的数中与n互质的数的数目。
例如\large φ(8)=4，因为\large 1,3,5,7均和\large 8互质。
解释：
1和8是互质的。互质是指两个数的最大公约数为1，而1和8的最大公约数就是1，因此它们是互质的
二、公式
如果n的唯一分解式：\large n=p_1^{r_1}\cdot p_2^{r_2} \cdot...\cdot p_k^{r_k}
有：
\large φ(n)= n\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2} \times ... \times \frac{p_k-1}{p_k}还是上面的栗子：
\large 8=2^3\large φ(8)=8*(1-\frac{1}{2})=4小结 下面三个公式，都需要依赖唯一分解定理：
\large n=p_1^{r_1}\cdot p_2^{r_2} \cdot...\cdot p_k^{r_k}
- ① 约数个数：只与幂次相关，与质因子无关 约数个数
=(1+r_1)\times (1+r_2) \times...\times (1+r_k)
- ② 约数和：与质数子和幂次都相关 约数和=
(p_1^0+p_1^1+p_1^2+...+p_1^{r_1}) \times (p_2^0+p_2^1+p_2^2+...+p_2^{r_1}) \times ... \times (p_k^0+p_k^1+p_k^2+...+p_k^{r_k})- ③ 欧拉函数公式，只与因子相关，与指数无关！ 欧拉函数=
n\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2} \times ... \times \frac{p_k-1}{p_k}
三、欧拉函数公式证明
欧拉函数的证明是使用的融斥原理，从定义出发：
定义：欧拉函数是小于n的数中与n互质的数的数目。
- ① 对数字
n进行质因数分解：
\large n={p_1}^{r_1} \cdot {p_2}^{r_2} \cdot {p_3}^{r_3} \cdot ... \cdot {p_k}^{r_k}- ② 如果一个数包含了
\large p_1这个因子，那么它肯定与n不互质，因为有\large p_1这个公因子嘛，换句话说，就是要想与n互质，那么一定不能包含\large p_1,p_2,...,p_k这些因子。
小于n的所有数字中，如果它包含了\large p_1,p_2,...,p_k这样的因子的话，那么它就与n不互质，换句话说，只要把小于n之内，所有包含\large p_1,p_2,..p_k的数字都干掉，剩下的就是与n互质的数。所谓包含\large p_1,p_2,..,p_k其实也就是 \large p_1,p_2,..,p_k的整数倍。
- 把
\large p_1的倍数从\large n中减去，那需要减去多少个呢？
答：\large \displaystyle \left \lfloor \frac{n}{p_1} \right \rfloor个.
注：这里想不明白的话，可以举个栗子：比如
n=10，p_1=2,有几个p_1的倍数呢？5个!为什么呢？
\large \displaystyle \left \lfloor \frac{10}{2} \right \rfloor=5-
③ 把
\large p_2,p_3,...,p_k的倍数都减去吧，分别减去\large \left \lfloor \frac{n}{p_2}\right \rfloor,\large \left \lfloor \frac{n}{p_3}\right \rfloor,...,\large \left \lfloor \frac{n}{p_k}\right \rfloor个。 -
④ 这么干是减多了的，比如某个数，是
\large p_2的倍数，也是\large p_3的倍数，就减了两回，还需要再加回来\large p_i * p_j的倍数，就是 +\large \frac{n}{p_1 * p_2}+\large \frac{n}{p_1 * p_3}+\large \frac{n}{p_1 * p_k}+ ....
-⑤ 将公式\large \phi(n)=n * (1-\frac{1}{p_1}) * (1-\frac{1}{p_2}) * (1-\frac{1}{p_3}) * ... * (1-\frac{1}{p_k})展开，发现就是上面的东东了，证毕。
变形： $\large \phi(n)=n * (1-\frac{1}{p_1}) * (1-\frac{1}{p_2}) * (1-\frac{1}{p_3}) * ... * (1-\frac{1}{p_k}) \ \Leftrightarrow \ \phi(n)=n * (\frac{p_1-1}{p_1}) * (\frac{p_2-1}{p_2}) * (\frac{p_3-1}{p_3}) * ... * (\frac{p_k-1}{p_k})$
四、求单个数字的欧拉函数
#include <bits/stdc++.h>
using namespace std;
// 求单个数的欧拉函数值
int phi(int x) {
int res = x;
// 不要写在i*i<=x, 可能会造成爆int
for (int i = 2; i <= x / i; i++)
if (x % i == 0) { // 暴力枚举所有因子
res = res / i * (i - 1); // 套一下欧拉函数公式
while (x % i == 0) x /= i; // 只与质因子有关，与幂次无关，应除尽除
}
if (x > 1) res = res / x * (x - 1); // 最后一个大因子
return res;
}
int main() {
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
printf("%d\n", phi(x));
}
return 0;
}
五、线性筛法求欧拉函数
依托于线性筛法，可以顺带求出欧拉函数值。如果对数论了解更多，会知道线性筛法还可以求出很多其它的东西。
phi[1]=1。φ(1)被定义为1
对区间内每个数进行分情况讨论：
- 如果这个数是质数，那么质数
i的欧拉函数值是phi[i]=i-1比如7，那么1-6当中有多少个数与7互质呢？显然6个都是嘛。 - 如果这个数不是质数，那么数字
i在被primes[j]尝试筛的过程中：(这里设p_j=primes[j]以简便下面的书写)
推论1：如果i\ \% \ p_j = 0, 那么 phi[i \times p_j] = phi[i] \times p_j
证明：
\large \because i={p_1}^{r_1} * {p_2}^{r_2} * {p_3}^{r_3} * ... *{p_j}^{r_j}*...*{p_k}^{r_k} 【算术基本定理】
i \times p_j分解质数因数的结果，只比i多分解了一个p_j，而 i \ \% \ p_j = 0 说明i中存在p_j因子，只不过指数增加了1个。
\large \therefore i \times p_j ={p_1}^{r_1} \times {p_2}^{r_2} \times {p_3}^{r_3} \times ... \times{p_j}^{r_j+1}\times...\times{p_k}^{r_k}
\large \phi{(i)}= i \times (1- \frac{1}{p_1}) \times (1- \frac{1}{p_2}) \times (1- \frac{1}{p_3}) \times ... \times (1- \frac{1}{p_j}) 【欧拉公式】
我们发现，欧拉公式只与质数因子相关，而与质数因子的幂次无关！ 二者的质数因子没有变化，变化的只是某个质数因子的幂次。所以:
\large \phi{(i \times p_j)} = i \times p_j \times (1- \frac{1}{p_1}) \times (1- \frac{1}{p_2}) \times (1- \frac{1}{p_3}) \times ... \times (1- \frac{1}{p_j}) = \phi{(i)} \times p_j
证毕
推论2: 如果i\ \% \ p_j > 0, 那么 phi[i \times p_j] = phi[i] \times (p_j-1)
证明：
\large \because i={p_1}^{r_1} * {p_2}^{r_2} * {p_3}^{r_3} * ... *{p_k}^{r_k}
\large \phi{(i)}= i \times (1- \frac{1}{p_1}) \times (1- \frac{1}{p_2}) \times (1- \frac{1}{p_3}) \times ... \times (1- \frac{1}{p_k})
p_j*i分解质数因数的结果，只是比i多分解了一个p_j，而 i \ \% \ p_j>0 说明i中不存在p_j这个因子，需要写上去。
\large p_j \times i ={p_1}^{r_1} \times {p_2}^{r_2} \times {p_3}^{r_3} \times ... \times {p_k}^{r_k} \times {p_j}^{1}
\large \therefore \phi{(p_j * i)}= p_j * i * (1- \frac{1}{p_1}) * (1- \frac{1}{p_2}) * (1- \frac{1}{p_3}) * ... * (1- \frac{1}{p_k}) * (1- \frac{1}{p_j})
\large \therefore \phi{(p_j * i)}= p_j \times \phi{(i)} \times (1 - \frac{1}{p_j}) = \phi{(i)} \times ( p_j -1)
【证毕】
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
// 筛法求欧拉函数
// 这个东西就在欧兰筛的基础上，加上题解中证明的公式，只能是背下来，没有别的办法
int primes[N], phi[N], st[N];
int cnt, res;
void get_eulers(int n) {
phi[1] = 1; // 1的欧拉函数值是1，这个是递推的起点
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
phi[i] = i - 1; // ①质数,则phi(i)=i-1
}
for (int j = 0; primes[j] <= n / i; j++) {
int t = primes[j] * i;
st[t] = 1;
if (i % primes[j] == 0) {
phi[t] = phi[i] * primes[j]; // ② i%pj==0
break;
} else
phi[t] = phi[i] * (primes[j] - 1); // ③i%pj>0
}
}
}
signed main() {
int n;
cin >> n;
// 筛法求欧拉函数
get_eulers(n);
// 累加欧拉函数值
for (int i = 1; i <= n; i++) res += phi[i];
printf("%lld\n", res);
}
六、欧拉定理
n 和 a 为正整数，且 n,a 互素，即gcd(n,a)=1，则：
$a^{\phi(n)} \equiv 1 (mod \ n讲解视频 证明挺麻烦的，有兴趣可以看一看，我就不证明了~
#### 用途 这个定理可以用来 简化幂的模运算。
基本例子
比如计算7^{222}的个位数，实际是求7^{222}被10除的余数。7和10 互素 ，且φ(10)=4。由欧拉定理知
7^4 \equiv 1(mod \ 10) \ (a=7,n=10)所以7^{222}=(7^4)^{55}*7^2 \equiv 1^{55}*7^2 \equiv 49 \equiv 9 (mod \ 10)
所以，答案是9。
复杂例子
求3333^{5555}的 个位 是什么。
很明显不可能直接把3333^{5555}的结果计算出来，那样太大了。但我们想要确定的是3333^{5555} \%10 ，问题就简单了:
- 我们知道
3333^{5555} \%10=3^{5555}\%10
\\
- 因为要求的是末位，也就是
\%10的结果，想要使用 欧拉定理:3与10互质\phi(10)=4,需要想办法构造5555里面有多少个4，可以直接把4的倍数直接约掉:
根据 模运算规则(a * b) \% p = (a \% p * b \% p) \% p，由于5555 = 4 * 1388 + 3，我们得到
3^{5555}\%10=(3^{4*1388} * 3^3)\%10=(3^{4*1388}\%10* 3^3\%10)\%10=(3^{4*1388}\%10* 27\%10)\%10=(3^{4*1388}\%10* 7)\%10
欧拉定理 出场!
对于3^{4*1388}而言，3^{4*1388} = (3^4)^{1388}
(3^4)中\phi(n) =\phi(10)= 4,即n = 10(1，3，7，9满足);
同时 满足3和10互质，所以3^{4*1388}=(1\%10)^{1388} = 1
所以(3^{4*1388}\%10* 7)\%10= (1 * 7) \% 10 = 7
计算完毕,答案是7。
七、一些性质
性质1
当 gcd(n,m)=1时， \large \phi(nm)=\phi(n) \times \phi(m)
从定义上来证明：
假设有两个互质的正整数n,m，则
\large \phi(n)=n \prod (1-\frac{1}{p_i}) \large \phi(m)=m \prod (1-\frac{1}{p_i'}) \large \phi(n)\times \phi(m)=n \prod (1-\frac{1}{p_i}) \times m \prod (1-\frac{1}{p_i'})=nm \prod(1-\frac{1}{p_i}) \prod(1-\frac{1}{p_i'}) 因为n,m互质，所以p_i和p_i′各各都不相同，且都是n,m的质因子
因此就可以推出φ(nm)=φ(n)φ(m)
至此，积性函数的性质得证。但是由上面的证明可知，n,m必须要互质才可以满足欧拉函数是 积性函数，由此可见 欧拉函数不是完全积性函数
性质2
当 n 为奇数时, \phi(2*n)=\phi(n)
证明
根据上面的性质2,当 n 为奇数时， n 与 2 互质，
\large \phi(2*n)=\phi(2)\times \phi(n)又因为\large \phi(2)=1$$
所以 \large \displaystyle \phi(2*n)=\phi(n)
性质3
若 n=p^k ， 则 \large \phi(n)=p^k*\frac{p-1}{p}=p^k-p^{k-1}=p^{k-1}(p-1)
性质4
当n>2时，所有小于n且与n互质的数和\large \displaystyle =\frac{n \times \phi(n)}{2},并且\phi(n) 为偶数
证明
需要知道的一个基本事实是 gcd(n,x)=gcd(n,n-x) \ \ \ \ (n>x)
注：关于这个，可以了解一下 更相减损术 也可以证明一下： 反证法，假设
n与x互质，n与n-x不互质 设n和n-x的最大公约数为m，则n=p*m，n-x=q*m所以x=(p-q)*m，推导出x和n有公约数m，与假设矛盾
因为 gcd(n,x)=gcd(n,n-x)(n>x) ，所以与n互质的数都是 成对出现 的
每一对的和都为 n 。所以他们的和为 \phi(n) \times n \div 2 。
至于 \phi(n)(n>2) 为偶数。因为与 n互质的数都是成对出现的，所以显然与 n互质的数为偶数，即 \phi(n) 为偶数。
性质5
若 p|n 且 p^2|n ，则
\large \phi(n)=\phi(\frac{n}{p})* p若p \mid n且p^2 \nmid n,则\large \displaystyle \phi(n)=\phi(\frac{n}{p})*(p-1)
证明
对于第一点
若 p \mid n 且 p^2 \mid n ，则证明 n 和 \frac{n}{p} 有相同的质因子，只是 p 这一项的指数不同
那么我们可以将其按照欧拉函数的计算式展开，并相除，可得：
\large \frac{n\prod_{i=1}^{m}(1-\frac{1}{p_i})}{\frac{n}{p}\prod_{i=1}^{m}(1-\frac{1}{p_i})}=\frac{n}{\frac{n}{p}}=p 对于第二点
若 p \mid n 且 p^2 \nmid n ，则说明 p 与 \frac{n}{p} 互质（因为 p 为素数）
那么根据欧拉函数为积性函数的这个性质即可证得
\large \phi(n)=\phi(\frac{n}{p})*\phi(p)=\phi(\frac{n}{p})*(p-1)证毕。
注： 这个性质广泛用于递推求欧拉函数,也就是筛法求欧拉函数的基础。
性质6
设\large n为一个正整数 ,\large \displaystyle n=\sum_{d \mid n}\phi(d)
证明 列出
\large \frac{1}{n},\frac{2}{n},\frac{3}{n},...,\frac{n}{n},一共 n个分数，再将他们化简．
最简分数\large \displaystyle \frac{a}{b}在上面出现的话，当且仅当 b|n且gcd(a,b)=1。
那么以b为分母的分数共ϕ(b)个。
分母一共被划分为 \large \displaystyle \sum_{d \mid n}1份．
所以
\large \displaystyle n=\sum_{d \mid n}\phi(d) 七、习题
题意：给定整数n，求[1,n]中与n 不互质 的数的和，最后mod\ 1e9+7
看一下上面的性质4证明,我们知道:设t为[1,n]中与n互质的数的和
\large t =\frac{n \times \phi(n)}{2}我们利用欧拉函数和欧几里德定理，if gcd(n,i)==1，则有 gcd(n,n-i)==1 ，可以知道其中一个若为i,则存在一个为n-i, 那么二者之和为n ，这样的一共有\phi(n)/2对, 故与n互质的所有数的和为 n \times \phi(n)/2 ,那么与n 不互质的数就是
\large n \times (n-1)/2-n \times \phi(n)/2#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int MOD = 1e9 + 7;
// 求单个数值的欧拉函数值
int phi(int x) {
int res = x;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
signed main() {
int n;
while (cin >> n && n) {
// 小于n的数字中有多少个数字与n互质
int ans = n * (n - 1) / 2; // 高斯公式，(首页+末项)*项数/2
ans = (ans - phi(n) * n / 2) % MOD; // 扣除掉 phi(n)*n/2
cout << ans << endl;
}
}
#include <bits/stdc++.h>
using namespace std;
// https://blog.csdn.net/skywalkert/article/details/43955611
// https://www.cnblogs.com/shuguangzw/p/5697183.html
// 指数循环节问题
// https://blog.csdn.net/acdreamers/article/details/8236942
map<int, int> f;
int pow(int x, int k, int p) {
int ret = 1;
while (k) {
if (k & 1)
ret = (long long)ret * x % p;
x = (long long)x * x % p;
k >>= 1;
}
return ret;
}
int phi(int x) {
int ret = x;
for (int i = 2; i * i <= x; ++i)
if (x % i == 0) {
ret -= ret / i;
while (x % i == 0)
x /= i;
}
if (x > 1)
ret -= ret / x;
return ret;
}
int F(int x) {
if (f.count(x))
return f[x];
int p = phi(x);
return f[x] = pow(2, F(p) + p, x);
}
int main() {
int t, n;
scanf("%d", &t);
f[1] = 0;
while (t--) {
scanf("%d", &n);
printf("%d\n", F(n));
}
return 0;
}