素数
线性筛
每个合数被最小质因子筛掉
用线性筛可求 (phi) 、(mu) 等积性函数
int p[N],prime[N],pnum;
void getp(){
for(int i=2;i<N;i++) p[i]=1;
for(int i=2;i<N;i++){
if(p[i]) prime[pnum++]=i;
for(int j=0;j<pnum && 1ll*i*prime[j]<N;j++){
p[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
}
试除法判断素数
用2~ (sqrt{n}) 试除
bool isprime(int x){
for(int i=2;i*i<=x;i++)
if(x%i==0) return false;
return true;
}
Miller-Rabin素性测试
Pollard-Rho分解质因数
最大公约数
最大公约数与最小公倍数
辗转相除法
int gcd(int a,int b) { return b?gcd(b,a%b):a; }
(lcm(a,b)=frac{ab}{gcd(a,b)})
翡蜀定理
若 (a,b) 为整数，(gcd(a,b)=d)，则对任意整数 (x,y) ，(ax+by=z)，(d|z)
存在不止一组 (x,y) 使 (ax+by=d)
扩展欧拉定理
用来求一组 (x,y) 满足 (ax+by=gcd(a,b))
推导：
要求 (ax+by=gcd(a,b)=gcd(b,a%b))
假设已求出 (by'+(a-(a/b)b)x'=gcd(b,a%b))
则 (x=x',y=y'-(a/b)x')
int extgcd(int a,int b,int &x,int &y) { //return gcd
if(b==0) { x=1; y=0; return a; }
int z=extgcd(b,a%b,y,x);
y-=(a/b)*x;
return z;
}
若已求出一组解 (x_0,y_0)
则任意解满足 (x=x_0+k imes frac{b}{gcd(a,b)},y=y_0-k imes frac{a}{gcd(a,b)})
费马小定理
费马小定理
若 (p) 为素数，(gcd(a,p)=1) ，则 (a^{p-1} equiv 1(mod p))
也即对任意整数 (a) ，(a^p equiv a(mod p))
证明
构造 (p) 的完全剩余系 (A={0,1,2,dots ,p-1 })
取满足 (gcd(a,p)=1) 的数 (a) ，则 (B={0a,a,2a,dots,(p-1)a }) 也为 (p) 的完全剩余系
（可以反证，若有两个数模 (p) 同余，即 (aiequiv aj(mod p))，则 (ai-ajequiv a(i-j) equiv i-j equiv 0 (mod p))，则 (i,j) 相等）
去掉0，则 (1 imes 2 imes dots imes (p-1) equiv a imes 2a imes dots imes (p-1)a (mod p))
即 (1equiv a^{p-1} (mod p))
欧拉定理
欧拉函数
(phi(n)) 表示 1~ (n) 中与 (n) 互质（(gcd(i,n)=1)）的数的个数
设 (n) 的质因子为 (p_1,p_2,dots ,p_m)
则 (phi(n)=nprodlimits_{i=1}^m frac{p_i-1}{p_i})
一些性质：
- (phi(1)=1)
- 若 (n) 为质数，则 (phi(n)=n-1)
- 积性函数——若 (m,n) 互质，则 (phi(nm)=phi(n)phi(m))
- 小于 (n) 且与 (n) 互质的数之和为 (frac{nphi(n)}{2}) ((n>1))
用线性筛求。
int phi[N],prime[N],pnum;
int getphi(){
phi[1]=1;
for(int i=2;i<N;i++) phi[i]=i-1;
for(int i=2;i<N;i++){
if(phi[i]==i-1) prime[pnum++]=i;
for(int j=0;j<pnum && 1ll*i*prime[j]<N;j++){
if(i%prime[j]==0) {
phi[prime[j]*i]=phi[i]*prime[j];
break;
}
phi[prime[j]*i]=phi[i]*(prime[j]-1);
}
}
}
求一个数的欧拉函数，要先分解质因数
int tot,fac[N];
void get_prime(int x){
int y=x;
tot=0;
for(int i=2;i*i<=y;i++){
if(y%i) continue;
fac[++tot]=i;
while(y%i==0) y/=i;
}
if(y!=1) fac[++tot]=y;
}
int phi(int x){
int ret=x;
get_prime(x);
for(int i=1;i<=tot;i++) ret=ret/fac[i]*(fac[i]-1);
return ret;
}
欧拉定理
对任意数 (p) ，若 (gcd(a,p)=1)，则 (a^{phi(p)}equiv 1(mod p))
证明：
取缩系 (A={r_1,r_2,dots,r_{phi(p)}})
则 (B={ar_1,ar_2,dots,ar_{phi(p)}}) 也为缩系
（反证：若(ar_iequiv ar_j(mod p))，则 (ar_i-ar_jequiv a(r_i-r_j) equiv r_i-r_j equiv 0 (mod p))，则 (r_i,r_j) 相等）
还是都乘起来就得到 (a^{phi(p)}equiv 1(mod p))
可以发现费马小定理是欧拉定理的特殊情况。
扩展欧拉定理
(
egin{equation}
a^bequiv
egin{cases}
a^{b\% phi(p)}& gcd(a,p)=1\
a^b& b<phi(p)\
a^{b\% phi(p)+phi(p)}& gcd(a,p)
eq 1,bgeq phi(p)
end{cases}
(mod p)
end{equation}
)
并不会证……
威尔逊定理
当且仅当 (p) 为素数时，((p-1)!equiv p-1 equiv -1(mod p))
逆元
定义（我自己说的）：当 (gcd(a,p)=1) 时，满足 (a imes b equiv 1(mod p)) 的小于 (p) 的数 (b) 为 (a) 对 (p) 的逆元
求法：
- (p) 为质数：费马小定理 (a^{p-2}equiv frac{1}{a} (mod p))
- (p) 不是素数：欧拉定理 (a^{phi(p)-1} equiv frac{1}{a} (mod p))
- 扩展欧几里得：(axequiv 1 (mod p) Rightarrow ax+py=1)
- 线性筛1~ (n) 的逆元： (inv[1]=1, inv[i]=p-(p/i) imes inv[p\%i] \% p)
阶与原根
阶
若 (gcd(a,p)=1) ，定义满足 (a^lequiv 1(mod p)) 的最小的 (l) 称为 (a) 模 (p) 的阶。
记为 (ord_p a)
一些性质：
- 对任意使 (a^l equiv 1 (mod p)) 的 (l) ，有 (ord_p a |l)。由欧拉定理，(ord_p a| phi(p))
- (1,a,a^2,dots,a^{ord_pa-1}) 关于模 (p) 互不同余
- 若 (ord_pa=l)，则 (ord_p a^t=frac{l}{gcd(t,l)})
- (a^iequiv a^j(mod p)) 当且仅当 (iequiv j(mod ord_pa))
原根
若 (gcd(g,p)=1) 且 (ord_pg=phi(p))，则称 (g) 为模 (p) 的原根。
一些性质：
- 若 (g) 为模 (p) 的原根，则 (A={g,g^2,dots,g^{phi(p)}}) 构成 (p) 的既约剩余系
- 有原根的数：1,2,4,(p^a),(2p^a) 其中 (p) 为奇素数，(a) 为正整数
- 判定原根：设 (p_1,p_2,dots,p_m) 是 (phi(n)) 的所有质因数，则 (g) 是模 (n) 的原根当且仅当 对任意 (1leq i leq m) ，有 (g^{frac{phi(n)}{p_i}} e 1 (mod n)) （找不到不同余号所以用的不等于号）
- 若 (p) 有原根，则 (p) 的原根有 (phi(phi(p))) 个（证明：设 (g) 为一个原根，则 (g^t) 为原根当且仅当 (frac{phi(p)}{gcd(phi(p),t)}=phi(p))，所以共 (phi(phi(p))) 个）
- (p) 的最小原根在 (O(p^{0.25})) 级别，可暴力求
小技巧：利用原根 (g) 可将一个与 (p) 互质的数表示为 (g^t)，指标 (t) 可方便一些运算或帮助发现性质。
bool check(int x,int p){ //判断x是否为模p原根
int q=Phi(p); //phi(p) 的质因子在 fac[]中，共tot个
for(int i=1;i<=tot;i++)
if(Pow_mod(x,q/fac[i],p)==1) return false;
return true;
}
int getg(int p){ //求最小原根，若无原根则返回0
if(p==1 || p==2) return 1;
if(p==4) return 3;
//判断有
int q=p,r;
if(p%2==0) q/=2;
for(int i=2;i*i<=q;i++)
if(q%i==0) { r=i; break; }
if(!isprime(r)) return 0;
while(q%r==0) q/=r;
if(q!=1) return 0;
for(int i=2;i<p;i++)
if(gcd(i,p)==1 && check(i,p)) return i;
}
int get_all_g(int p){ //求所有原根，存入 A[]，返回原根数量
int g=getg(p),z=Phi(p);
if(!g) return 0;
int ret=0; A[++ret]=g;
for(int i=2;i<=z;i++) if(gcd(i,z)==1) A[++ret]=Pow_mod(g,i,p);
return ret;
}
BSGS
BSGS
给定 (a,b,p)，(gcd(a,p)=1)，(p) 为质数，求最小非负整数 (x) 满足 (a^xequiv b(mod p))
由于 (p) 为质数，所以若有解，则最小非负整数解一定满足 (xleq p-1)
分块，将 (a^x) 写成 (a^{im-j})，其中 (m=lceil sqrt{p}
ceil,0leq i,jleq lceil sqrt{p}
ceil)
则 ((a^m)^i imes a^{-j} equiv b(mod p) Rightarrow (a^m)^iequiv b imes a^j(mod p))
存下来所有 (ba^j) ，然后从小到大枚举 (i) ，判断是否有与 ((a^m)^i) 相等的 (ba^j)
不要用 (map) ，要用哈希表存……
注意可能无解！！！
vector<Pr> hs[4987657];
int Hash(int x) { return (1ll*x*x%4987657+x%100007)%4987657; }
void ins(Pr x){
int id=Hash(x.fi);
hs[id].pb(x);
}
int has(int x){
int id=Hash(x);
for(int i=0;i<hs[id].size();i++)
if(hs[id][i].fi==x) return hs[id][i].se;
return -1;
}
int BSGS(int a,int b,int p){
int m=ceil(sqrt(p)),q=Pow_mod(a,m,p); //a^(im-j)=b(mod p)
for(int i=0,cur=1;i<=m;i++){
ins(Pr(1ll*cur*b%p,i));
cur=1ll*cur*a%p;
}
for(int i=1,cur=q;i<=m;i++){
int t=has(cur);
if(t!=-1) return i*m-t;
cur=1ll*cur*q%p;
}
return -1;
}
扩展BSGS
给定 (a,b,p)，(gcd(a,p)=1)，(p) 不一定为质数，求最小非负整数 (x) 满足 (a^xequiv b(mod p))
如果 (gcd(a,p)=1) ，那么 (x<p) ，仍可用 (BSGS) 求解。
否则，设 (d=gcd(a,p))
若 (d
mid b) 则无解
否则写成 (frac{a}{d} imes a^{x-1} equiv frac{b}{d} (mod frac{p}{d}))
由于此时 (gcd(frac{a}{d},frac{p}{d})=1)，所以可以把 (frac{a}{d}) 除到另一边
得到 (a^{x-1} equiv frac{b/d}{a/d} (mod/ p/d)) 子问题递归求解即可。
注意若某次 (b=1) ，则可直接返回0，不用再往下递归了
unordered_map<int,int> mp;
int BSGS(int a,int b,int p){
if(b==1) return 0;//!!!
int m=ceil(sqrt(p)),q=Pow_mod(a,m,p);
mp.clear();
for(int i=0,cur=b;i<=m;i++) mp[cur]=i,cur=1ll*cur*a%p;
for(int i=1,cur=q;i<=m;i++){
if(mp[cur] || cur==b) return i*m-mp[cur];
cur=1ll*cur*q%p;
}
return -1;
}
int extBSGS(int a,int b,int p){
int z=gcd(a,p),bb=b,pp=p,k=0;
while(z>1 && b!=1){ //a^(x-k)=bb(mod pp)
if(bb%z!=0) return -1;
//a/d * a^(x-k-1)=bb/d (mod pp/d)
bb/=z; pp/=z;
bb=1ll*bb*inv(a/z,pp)%pp;
z=gcd(a,pp); k++;
}
int ret=BSGS(a,bb,pp);
if(ret==-1) return -1;
ret+=k;
for(int i=k-1;i>=0;i--) if(Pow_mod(a,i,p)==b) ret=i;
return ret;
}
同余方程
一次同余方程
形如 (a_1x_1+a_2x_2+dots+a_nx_n equiv b(mod m)) 的方程
有解的充要条件是 (gcd(a_1,a_2,dots,a_n,m)|b) ，在模 (m) 意义下共 (m^{n-1} imes gcd(a_1,a_2,dots,a_n,m)) 个解
中国剩余定理
设正整数 (m_1,m_2,dots,m_n) 两两互质
求解同余方程组 (xequiv a_i(mod m_i))
在模 (M=prod m_i) 下有唯一解 (sumlimits_{i=1}^n frac{M}{m_i} imes a_icdot inv(frac{M}{m_i},m_i))
ll m[N],a[N];
int n;
ll crt(){
ll M=1;
for(int i=1;i<=n;i++) M=M*m[i];
ll ret=0;
for(int i=1;i<=n;i++){
ll mm=M/m[i];
ret=(ret+(inv(mm,m[i])*a[i])%m[i]*mm%M)%M; //注意有的地方模 m[i]
}
return ret;
}
扩展中国剩余定理
模数 (m_1,m_2,dots,m_n) 不一定互质
考虑合并两个方程 (xequiv a_1(mod m_1),xequiv a_2(mod m_2))
可写成 (x=pm_1+a_1=qm_2+a_2)
则 (pm_1-qm_2=a_2-a_1)
若 (gcd(m_1,m_2)
mid (a_2-a_1)) 则无解
否则求出一组满足条件的 ((p_0,q_0))，对应的 (x=p_0m_1+a_1)；而该方程组所有解为 (p=p_0+kfrac{m_2}{gcd(m_1,m_2)},q=q_0-kfrac{m_1}{gcd(m_1,m_2)})，所以对应的所有 (x=(p_0+kfrac{m_2}{gcd(m_1,m_2)})m_1+a_1=k imes (frac{m_1m_2}{gcd(m_1,m_2)})+p_0m_1+a_1)
方程转化为 (xequiv p_0m_1+a_1 (mod frac{m_1m_2}{gcd(m_1,m_2)}))
int n;
ll a[N],m[N];
ll extcrt(){
ll aa=a[1],mm=m[1];
for(int i=2;i<=n;i++){
ll x,y,z=extgcd(mm,m[i],x,y);
ll q=m[i]/z;
if(abs(aa-a[i])%z) return -1;
x=mul(x,(a[i]-aa)/z,q);
q=q*mm;
aa=x*mm+aa; mm=q;
}
return aa;
}
组合数取模
计算 (C_m^n \% p)
- (1leq m leq 10^3) 杨辉三角
- (1 leq m leq 10^6)，(p) 为质数：预处理 (mul[],inv[])
- (1leq mleq 10^6) ，(p)为较小合数：暴力分解质因数
- (1leq mleq 10^{18} ,1leq p leq 10^5) ，(p) 为质数：lucas定理
- (1leq m leq 10^{18}) ，(p) 不是质数：扩展lucas定理
lucas定理
对于质数 (p) ，(inom{n}{m} mod p=inom{n/p}{m/p} imes inom{n mod p}{m mod p} mod p)
ll C(int x,int y){ //x>y
if(y>x) return 0;
return (fac[x]*Pow_mod((fac[y]*fac[x-y])%P,P-2))%P;
}
ll lucas(int x,int y){
if(y==0) return 1;
return (C(x%P,y%P)*lucas(x/P,y/P))%P;
}