质数

1.试除法判断x是否为质数 $O(\sqrt n)$

def is_prime(x):#判断x是否为质数
    if x<2:return False
    i=2
    while i<=x/i:
        if x%i==0:return False
        i+=1
    return True 

2.试除法分解质因数 $O(\sqrt n)$

#分解x的质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数
def divide(x):
    cnt=0
    i=2
    while i<=x/i:
        if x%i==0:
            while x%i==0:
                cnt+=1
                x//=i
            print(i,cnt)
            cnt=0
        i+=1
    if x>1:print(x,1) 

3.线性筛法求素数 $O(n)$

思路：每个合数都是用它的最小的质因数来被筛掉
i%primes[j]==0时没有退出的话，primes[j+1]*i就会被i筛掉
但是primes[j+1]*i的最小质因数是primes[j],因为i存在最小质因数primes[j]
所以primes[j+1]*i不应该由primes[j+1]来筛

primes=[]#存储1-n中的质数
st=[0]*(n+1)#判断i是否是合数（是否被筛掉）
def get_primes(n):
    for i in range(2,n+1):
        if st[i]==0:primes.append(i)#i还未被筛掉，可以加入质数数组
        j=0
        while primes[j]*i<=n:#用目前1-i中的质数去筛1-n中的合数
            st[primes[j]*i]=1
            if i%primes[j]==0:break#用最小的质因子去筛
            j+=1

约数

1.试除法求所有的约数$O(\sqrt n)$

def divisors(n):#求1-n中所有的约数，并排序
    res=[]
    i=1
    while i<=n//i:
        if n%i==0:
            res.append(i)
            if i!=n//i:res.append(n//i)
        i+=1
    res.sort()
    return res 

2.约数个数和约数之和 $O(\sqrt n)$

如果 N = p1^c1 * p2^c2 * … *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * … * (ck + 1) 所有质因数的个数+1的乘积
约数之和： (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)

约数个数

#求n个数乘积的约数的个数
mod=10**9+7
dic={}#映射质因数的个数
for i in range(int(input())):
    n=int(input())
    i=2
    while i<=n/i:
        while n%i==0:#质因数
            n//=i
            if i not in dic:dic[i]=1
            else :dic[i]+=1
        i+=1
    if n>1:
        if n not in dic:dic[n]=1
        else:dic[n]+=1
res=1
for i in dic: 
    res=res*(dic[i]+1)%mod
print(res)

约数之和

mod=10**9+7
dic={}
for i in range(int(input())):
    n=int(input())
    i=2
    while i<=n/i:
        while n%i==0:
            n//=i
            if i not in dic:dic[i]=1
            else:dic[i]+=1
        i+=1
    if n>1:
        if n not in dic:dic[n]=1
        else:dic[n]+=1
res=1
for i in dic:
    q=i
    n=dic[i]
    res=res*(1-q**(n+1))//(1-q)%mod # q^0+q^1+...+q^n
print(res)

欧拉函数

引理1：欧拉函数是积性函数。当$m$和$n$互质时，$\phi(mn)=\phi(m)+\phi(n)$
证明：m和n互质，所以他们没有相同的质因子。在[1,mn]中有且仅有既与m互质又与n互质的数与mn互质

欧拉函数的定义：$\phi(N)$=在[1,N]中与N互质的数的个数(互质：两个数的公因数只有1这个数,1和任何数互质)
$N=p_1^{a_1}p_2^{a_2}…p_m^{a_m}$
根据欧拉函数是一个积性函数得:
$$\phi(N)=\phi(p_1^{a_1}) \times… \times\phi(p_m^{a_m})$$
$\phi(p_k^{a_k})$=$[1,p_k^{a_k}]$中与$p_k^{a_k}$互质的数的个数
$[1,p_k^{a_k}]$中与$p_k^{a_k}$不互质的数是$p_k\*(1,2,3…,p_k^{a_k-1})$,一共$p_k^{a_k-1}$个数
所以 $$\phi(p_k^{a_k})=p_k^{a_k}-p_k^{a_k-1}=p_k^{a_k}\*(1-\frac{1}{p_k})$$
$$\phi(N)$$
$$=\phi(p_1^{a_1}) \times… \times\phi(p_m^{a_m})$$
$$=p_1^{a_1}\frac{1}{p_1}\times…\times p_m^{a_m}\frac{1}{p_m}$$
$$=p_1^{a_1} p_2^{a_2}…p_m^{a_m}\times (\frac{1}{p_1}\times…\times\frac{1}{p_m})$$
$$=N\times\frac{1}{1-p_1}…\frac{1}{1-p_m}$$
$p_1,p_2,…,p_m$就是$n$的各个质因数

1.求一个数的欧拉函数$O(\sqrt n)$

def phi(n): #求欧拉函数φ(n)
    res=n
    while i<=n/i:#求n的质因子
        if n%i==0:
            res=res*(i-1)//i
            while n%i==0:
                n//=i
        i+=1
    if n>1:res=res*(n-1)//n
    return res

2.线性筛法求欧拉函数$O(n)$

N=10**6+1
e=[0]*N
st=[0]*N
primes=[]
def get(n):
    for i in range(2,n+1):
        if st[i]==0:
            primes.append(i)
            e[i]=i-1
        j=0
        while primes[j]*i<=n:
            st[primes[j]*i]=1
            if i%primes[j]==0:
                e[primes[j]*i]=e[i]*primes[j]
                break
            e[primes[j]*i]=e[i]*(primes[j]-1)
            j+=1

快速幂

1.快速幂求$a^b\%p\quad O(\log_2 n)$

def qmi(a,b,p):
    res=1
    while b:
        if b&1:
            res=res*a%p
        a=a*a%p
        b>>=1
    return res 

欧拉定理：若$a$与$n$互质，则有$a^{\phi(n)}\equiv1(\mod n)$
证明：设与$n$互质的是集合$Z=[x_1,x_2,…,x_{\phi(n)}]$共$\phi(n)$个元素
再设集合$S=[m_1,m_2,…,m_{phi(n)}]$
其中$m_i=a\*x_i\%n$,即$a$和集合$Z$中的每个数的乘积再模$n$
所以集合$S$中的每个数都与$n$互质，且集合中的数都互不相同
因为[1,n]与$n$互质的数就是$\phi(n)$个
所以$Z=S$
所以$ax_1\*ax_2\*…\*ax_{phi(n)}\equiv x_1\*x_2\*…\*x_{phi(n)}(\mod n)$
根据余数定理，等式两边同时约掉相同的数后，模出来的结果还是相同的
所以$a^{\phi(n)}\equiv1(\mod n)$
费马小引理:当$n$为质数时，$a^{n-1}\equiv 1(\mod n)$
乘法逆元：若$a$和$n$互质，$a\*b\equiv1(\mod n)$，则$b$为$a$模$n$的逆元
求乘法逆元：
1.当$a$和$n$不互质时，不存在乘法逆元
2.当$n$为质数时，由费马小引理得$b=a^{n-2}\%n$
3.当$n$不是质数时，用扩展欧几里得求逆元

2.快速幂求逆元(仅当n为质数时)$O(log_2n)$

for i in range(int(input())):
    a,p=map(int,input().split())
    if a%p==0:print("impossible")
    else:
        res=pow(a,p-2,p)
        print(res)

扩展欧几里得算法

对于每对a和b，求出一组x和y使得$ax+by=gcd(a,b)$
利用gcd算法，gcd(a,b)=gcd(b,a%b)
$bx+(a-a//b*b)y=gcd(a,b)$
$ay+b(x-a//by)=gcd(a,b)$
所以当b,a%b对应x,y时
a,b对应y,x-a//by
可以用递归求解

1.扩展欧几里得算法$O(log_2(a+b)$

def exgcd(a,b,x,y):
    if b==0:
         return a,1,0
    d,x,y=exgcd(b,a%b,x,y)
    x,y=y,x-a//b*y
    return d,x,y#d为gcd(a,b)
for i in range(int(input())):
    a,b=map(int,input().split())
    x,y=0,0
    _,x,y=exgcd(a,b,x,y)
    print(x,y)

2.扩展欧几里得算法求解线性同余方程

求$x$满足$a\*x\equiv b(\mod m)$
即求x满足$ax+my\equiv b(\mod m)$
根据裴蜀定理：存在x,t满足$ax+my=gcd(a,m)$
当b是gcd(a,m)的倍数的时候，等式两边同乘上$b//gcd(a,m)$，就变成了$b//gcd(a,m)ax+b//gcd(a,m)my=b$
所以求得解为$b//gcd(a,m)x$

求解线性同余方程$O(log_2(a+b)$

def exgcd(a,b,x,y):
    if b==0:
        return a,1,0
    d,x,y=exgcd(b,a%b,x,y)
    x,y=y,x-a//b*y
    return d,x,y
for i in range(int(input())):
    a,b,m=map(int,input().split())
    x,y=0,0
    d,x,y=exgcd(a,m,x,y)
    if b%d==0:print(b//d*x%m)
    else :print("impossible")

求解逆元$O(log_2(a+b)$

def exgcd(a,b,x,y):
    if b==0:
        return a,1,0
    d,x,y=exgcd(b,a%b,x,y)
    x,y=y,x-a//b*y
    return d,x,y
for i in range(int(input())):
    a,m=map(int,input().split())
    b=1
    x,y=0,0
    d,x,y=exgcd(a,m,x,y)
    if b%d==0:print(b//d*x%m)
    else :print("impossible")

求组合数

1.递推$O(n^2)$

$C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}$
$f[i][j]=f[i-1][j-1]+f[i-1][j]$

mod=int(1e9+7)
N=2001
f=[[0]*N for i in range(N)]
f[0][0]=1
for i in range(1,N):
    for j in range(0,i+1):
        if j==0:f[i][j]=1
        else :f[i][j]=f[i-1][j-1]+f[i-1][j]
        f[i][j]%=mod
for i in range(int(input())):
    a,b=map(int,input().split())
    print(f[a][b])

2.快速幂+逆元$O(n)$

$C_n^m=n!\times m!^{-1}\times (n-m)!^{-1}$

from sys import stdin
N=int(1e5+1)
mod=int(1e9+7)
fact=[0]*N#求i!
infact=[0]*N#求i!^-1
fact[0]=1
infact[0]=1
for i in range(1,N):
    fact[i]=fact[i-1]*i%mod
    infact[i]=pow(fact[i],mod-2,mod)
for i in range(int(stdin.readline())):
    n,m=map(int,stdin.readline().split())
    res=fact[n]*infact[m]%mod*infact[n-m]%mod
    print(res)

容斥原理

from sys import stdin
n,m=map(int,stdin.readline().split())
p=list(map(int,stdin.readline().split()))
res=0
for i in range(1,1<<m):#从1开始，至少整除一个
    s=1
    cnt=0
    for j in range(m):
        if i>>j&1:
            if p[j]*s>n:
                s=-1
                break
            s*=p[j]
            cnt+=1
    if s!=-1:
        if cnt%2==0:res-=n//s
        else :res+=n//s
print(res)

博弈论

1.Nim游戏

假设只有两堆且石子一样，先手从其中一堆中拿出石子，后手一定能从另外一堆中拿出同样的石子。只要先手有石子拿。后手也有石子拿。

res=0
n=int(input())
for i in list(map(int,input().split())):
    res^=i
if res==0:print("No")#异或值为0，表示所有的堆都是成对的
else :print("Yes")