欧拉函数
什么是欧拉函数
欧拉函数\(\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