【算法】欧拉函数、快速幂、容斥原理

欧拉函数

内容：表示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_1{p}_2}+\frac{N}{p_2{p}_3}$$

​ 以此类推，利用容斥原理的思想，可得：
$$\phi (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}modp$的结果，一般做法的时间复杂度是$O(k)$，快速幂的时间复杂度是$O(logk)$

思路：将k分解成2的指数幂相加，例如$2^5$的5可以转换为2进制形式101，因此$2^5$可以写为$2^{2^0}\times 2^{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}modp=1$成立的a值

[!note]

费马小定理：

如果 p 是素数，且 a 是整数，并且 a 不被 p 整除，那么：
$$a^{p-1}\equiv 1(modp)$$
注：如果能够整除的话是不可能会mod == 1的

​ 所以$\frac{b}{a}modp=1$可以写为$b\cdot xmodp=1$，利用费马小定理有：
$$b\cdot b^{p-2}\equiv 1(modp)$$
​ 即$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 # 偶数集合的交集要减

原文地址：https://blog.csdn.net/weixin_51908696/article/details/144073825

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！