欧拉函数
内容：表示1-n中与n互质的个数
原理：一个数可以被质因子表示，而除了质因子及其倍数，剩下的个数都是与n互质
推导（容斥原理）：
1-N总共有N个数，首先将质因子\(p_1,p_2...p_n\)中的倍数减去，因为质因子的倍数与n是不互质的，因此首先减去质因子倍数的个数：
\[N = N- \frac{N}{p_1}- \frac{N}{p_2}- \frac{N}{p_3} \] 又因为质因子\(p_1,\)\(p_2\)可能有公共的倍数数字，在这个过程可能被减掉两次（例如6是2，3的倍数，在上述过程中6会被减掉两次），因此还需要再加上一次，所以有：
\[N = N+ \frac{N}{p_1p_2}+ \frac{N}{p_2p_3} \] 以此类推，利用容斥原理的思想，可得：
\[\varphi(N)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k}) \]def ola(x):
res = x
for i in range(2, int(x/i) + 1):
if(x % i == 0):
while (x % i == 0):
x //= i
res *= ((i-1)/i)
if (x > 1) res*= ((x-1)/x)
- 筛法求欧拉函数
快速幂
内容：快速求出\(a^k\ mod \ p\)的结果，一般做法的时间复杂度是\(O(k)\)，快速幂的时间复杂度是\(O(logk)\)
思路：将k分解成2的指数幂相加，例如\(2^5\)的5可以转换为2进制形式101，因此\(2^5\)可以写为\(2^{2^0}\times2^{2^2}\)，最多只需要进行\(logk\)次操作
应用：快速幂求逆元
def qmi(x, k, p):
res = 1
while k:
if (k & 1) res *= (a % p)
k >>= 1
a = a * a % p
return res
- 求逆元
要求：已知b，求使得\(\frac{b}{a} \ mod \ p=1\)成立的a值
[!note]
费马小定理：
如果 p 是素数，且 a 是整数，并且 a 不被 p 整除，那么：
\[a^ {p−1}≡1 (mod\ p) \]注：如果能够整除的话是不可能会mod == 1的
所以\(\frac{b}{a} \ mod \ p=1\)可以写为\(b ·x \ mod \ p=1\)，利用费马小定理有：
\[b · b^{p-2}≡1 (mod\ p) \] 即\(a = b^{p-2}\)，最后只需利用快速幂求出\(b^{p-2}\)
容斥原理
- 能被整除的数
要求：求出1-n中可以被\(p_1,\)\(p_2,\)\(p_3...\)等质数至少一个整除的整数有多少个
# 求1-360中有多少个可以整除2，3，5的数字个数
p = [2, 3, 5]
n = 360
k = len(p) #表示一个有多少种集合个数，可以被2整除的为一个集合，可以被3整除的为一个集合...
for i in range(1 << k): # 二进制优化，i表示选择哪些集合，100（4）表示只有选择可以被2整除的集合，101（5）表示选择可以被2和5整除的集合
for j in range(k):
cnt = 0
t = 1
if (i >> j & 1): # 表示选取第k-j个集合
cnt += 1
if t * p[j] > n: # 说明目前所选择的集合在1-n的情况下不可能有交集，例如1-20中，不可能存在同时可以除以2 3 5的数字，最小的数字为2*3*5
t = -1
break
t *= p[j]
if t != -1:
if cnt % 2 != 0:
res += n / t # 奇数集合的交集要增
else:
res -= n / t # 偶数集合的交集要减