欧拉函数
什么是欧拉函数
欧拉函数\(\phi(n)\)：1 - n 中与 n 互质的数的个数
例如：\(\phi(6) = 2\)，1 - 6 中与 6 互质的数为 1、5
a，b互质就是gcd(a,b) = 1
如何求解欧拉函数
对于一个数N，可以分解质因数为\(N = P_{1}^{k_{1}} \times P_{2}^{k_{2}} \times \dots \times P_{n}^{k_{n}}\)，则\(\phi(N) = N \times (1 - \frac{1}{P_{1}}) \times (1 - \frac{1}{P_{2}}) \times \dots \times (1 - \frac{1}{P_{n}})\)
比如 \(6 = 2 \times 3\)，则\(\phi(6) = 6 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) = 2\)
证明
利用容斥原理
- 从1 - N 中 去除其全部质因子\(P_{1} \dots P_{n}\)的所有倍数，那么还剩下\(S_{1} = N - \frac{N}{P_{1}} - \frac{N}{P_{2}} - \dots - \frac{N}{P_{n}}\)个数
- 有的数既是\(P_{i}\)的倍数又是\(P_{j}\)的倍数因此被减了两遍，需要将这一部分加回来，\(S_{2} = S_{1} + \frac{N}{P_{1}\times P_{2}}+ \frac{N}{P_{1}\times P_{3}} + \dots + \frac{N}{P_{1}\times P_{n}} + \frac{N}{P_{2}\times P_{3}} + \dots +\frac{N}{P_{2}\times P_{n}} + \dots + \frac{N}{P_{n-1}\times P_{n}}\)
- 有的数是\(P_{i}\)、\(P_{j}\)、\(P_{k}\)的倍数，在第一步减了三次，在第二步加了三次，相当于没加也没减，因此需要减掉一次，因此\(S_{3} = S_{2} - \frac{N}{P_{i}\times P_{j} \times P_{k}}\)，\([i,j,k]\)是1 - n的一组排列
以此类推到第n步，化简就是上边的公式
代码模板
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;
}
！注意每一步计算\(res \times(1 - \frac{1}{i})\)可能会出现小数，可以转换为\(\frac{res}{i} \times (i - 1)\)就能保证结果是整数
筛法求欧拉函数
利用质数的线性筛法求1-n的欧拉函数
由于在线性筛法的执行过程中，对于质数会保留，对于合数会用其最小质因子筛掉。所以线性筛法是会访问到所有数的。而根据上面的推导，在遇到每种情况时，我们都能求出欧拉函数
-
当这个数是质数：\(\phi(i)=i-1\)
-
当这个数是合数：
某个合数一定是被\(`p_{j} \times i\)` 给删掉的，我们就在删他的时候求他的欧拉函数值
- 如果
i % pj == 0,那么pj就是i的某个质因数，那么\(`p_{j} \times i`\)和i的质因数组合完全相同，所以\(\phi(pj \times i) = pj \times \phi(i)\) - 如果
i % pj != 0,那么\(`p_{j} \times i`\)的质因数组合就是在i的质因数组合基础上加了一个pj,所以\(\phi(pj \times i) = pj * \phi(i) \times (1 - \frac{1}{pj}) = (pj - 1) \times \phi(i)\)
- 如果
代码模
int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
{
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
欧拉函数应用
欧拉定理：若a与n互质，那么有\(a^{\phi(n)}\) mod \(n=1\)
费马定理：若a与p互质，p是质数，那么有\(a^{\phi(p)}\) mod p \(= a^{p-1}\) mod p = 1
证明略
快速幂
可以快速的求出\(a^{k}\) mod \(p\) 的值，时间复杂度是\(O(logk)\)，其中a、k、p的范围都是\(10^{9}\)
核心思路：反复平方法
预处理出：\(a^{2^{0}}\) mod p、\(a^{2^{1}}\) mod p、\(a^{2^{2}}\) mod p、\(\dots\)、\(a^{2^{\log_{2}{k} }}\) mod p 一共
\(\log_{2}{k}\) 个数
当求 \(a^{k}\) mod \(p\) 时利用预处理的这些值组合出\(a^{k}\)，即将 \(a^{k}\) 拆成 \(a^{k} = a^{2^{x_{1}}} \times a^{2^{x_{2}}} \times \dots \times a^{2^{x_{t}}} = a^{2^{x_{1}}+2^{x_{2}}+\dots+2^{x_{t}}}\)
得到\(k=2^{x_{1}}+2^{x_{2}}+\dots+2^{x_{t}}\)，其实，就只需要把 k 转化为二进制即可
预处理一共计算出\(\log_2k\)个数，需要计算 \(log_2k\) 次，将 k 拆成二进制表示，并计算结果，需要 \(log_2k\) 次，所以总共的时间复杂度就是O(\(\log_2k\))。其实编写代码时，可以将上面两步合在一起，实际只需要 \(\log_2k\) 次运算，例如\(4^{5}=4^{(101)_{2}}=4^{2^{0}}\times 4^{2^{2}}\)
代码模板
typedef long long LL;
int qmi(int a, int k, int p) {
int res = 1;
while (k) {
if (k & 1) res = (LL)res * a % p;
k >>= 1;
a = LL(a) * a % p;
}
return res;
}
扩展欧几里得算法
裴蜀定理：对于任意正整数a，b，那么一定存在非零整数x，y，使得ax+by=gcd(a,b)
证明：令 gcd(a,b) = c ，则a一定是c的倍数，b也一定是c的倍数，那么ax+by也一定是c的倍数，那么可以凑出最小的倍数就是1倍，即ax+by=gcd(a,b)
给定a，b如何求解x，y就是扩展欧几里得算法
代码模板
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
扩展欧几里得算法用来解决这样一个问题，ax+by=m，求x，y，如果m是gcd(a,b)的倍数，则有解，解就是倍数乘以x，y，否则就是无解
此外，还可以解线性同余方程/方程组，例如解\(ax\equiv b (mod \ m)\)，做一下变换就是\(ax=km+b\)，即\(ax-km=b\)，就可以用扩展欧几里得算法解决，878. 线性同余方程
解方程组\(x\equiv a_{1}(mod \ m_{1})\)、\(x\equiv a_{2}(mod \ m_{2})\dots\)两两合并\(x=k_{1}m_{1}+a_{1}=k_{2}m_{2}+a_{2}\)，做一下变换\(k_{1}m_{1}-k_{2}m_{2}=a_{2}-a_{1}\)，有解的条件是\(a_{2}-a_{1}\)是\(gcd(m_{1},m_{2})\)的倍数，解出通解是\(k_{1}+k\frac{m_{2}}{d}\)、\(k_{2}+k\frac{m_{1}}{d}\)，其中\(d = gcd(m_{1},m_{2})\)，带入原式得\(x=(k_{1}+k\frac{m_{2}}{d})m_{1}+a1=k\ lcd(m_{1},{m2})+k_{1}m_{1}+a_{1}=km+a\)，其中\(m=lcd(m_{1},m_{2})\)，\(a=k_{1}m_{1}+a_{1}\)，这样就将两个方程合并成了一个方程，然后继续向后合并计算，直到只有一个方程就可以向上面的方式进行1iu
中国剩余定理
有k个两两互质的数\(m_{1}、m_{2}、\dots 、m_{k}\)，给定线性同余方程组\(x\equiv a_{1}(mod\ m_{1})\)、\(x\equiv a_{2}(mod\ m_{2})\)、… 、\(x\equiv a_{k}(mod\ m_{k})\)，求x
解法：令\(M=m_{1}\times m_{2}\times \dots \times m_{k}\)，
\(M_{i} = \frac{M}{m_{i}}\)，用\(M_{i}^{-1}\)表示\(M_{i}\) 模 \(m_{i}\) 的逆（\(M_{i} \times M_{i}^{-1} \equiv 1 (mod \ m_{i})\)）
则\(x=a_{1}\times M_{1} \times M_{1}^{-1} + a_{2}\times M_{2} \times M_{2}^{-1} + \dots + a_{k}\times M_{k} \times M_{k}^{-1}\)
标签：dots,phi,frac,int,times,数学知识,第四章,mod From： https://www.cnblogs.com/chenjq12/p/17115049.html