gcd and lcm
Code
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
gcd的几条性质
证明：
(gcd(x^a-1,x^b-1))
(=gcd(x^b-1,x^a-x^b))
(=gcd(x^b-1,x^b(x^{a-b}-1)))
(=gcd(x^b-1,x^{a-b}-1))
（ (fib[]) 为广义斐波那契数列）
证明：
(gcd(fib[i+j],fib[j]))
(=gcd(fib[j],fib[i+j]-fib[j]))
(=gcd(fib[j],fib[i-1]*fib[j]+fib[i]*fib[j+1]-fib[j]))
(=gcd(fib[j],fib[i]*fib[j+1]))
(=gcd(fib[j],fib[i]))
线性筛
int pr[maxn],tot;
bool check[maxn];
void init(int n){
check[1]=1;
for(int i=2;i<=n;i++){
if(!check[i]){
pr[++tot]=i;
}
for(int j=1;j<=tot&&i*pr[j]<=n;j++){
check[i*pr[j]]=1;
if(i%pr[j]==0)break;
}
}
}
理论上来讲 (n) 以内的质数个数大约在 (n/ln(n)) 个左右
欧拉定理
设 (S={x_1,x_2,...,x_{varphi(n)}}) 为所有与 (n) 互质且 (le n) 的数。
显然 (x_i≡x_j(i≠j)(\% n)) 不成立。
再设 (T={a*x_1,a*x_2,...,a*x_{varphi(n)}})
(ecause gcd(a,n)=1)
( herefore a*x_i≡a*x_j(i≠j)(\% n)) 不成立
( herefore S=T)
( herefore prod_{i=1}^{varphi(n)}a*x_i≡prod_{i=1}^{varphi(n)}x_i(\% n))
( herefore a^{varphi(n)}≡1(\% n))
扩展欧拉定理
费马小定理
(a^{p-1}≡1(\% p)(p ext{ is prime}))
Code
(O(n)) 求 (1-n) 的欧拉函数
void init(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!check[i]){
pr[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&i*pr[j]<=n;j++){
check[i*pr[j]]=1;
if(i%pr[j]==0){
phi[i*pr[j]]=phi[i]*pr[j];
break;
}
else phi[i*pr[j]]=phi[i]*phi[pr[j]];
}
}
}
(O(sqrt{n})) 求 (n) 的欧拉函数
int phi(int n){
int x=n,ret=n;
for(int i=2;i*i<=n&&x>1;i++){
if(x%i==0){
ret=ret/i*(i-1);
while(x%i==0)x/=i;
}
}
if(x>1)ret=ret/x*(x-1);
return ret;
}
逆元
逆元的引入
在做组合数取模的时候，常常要求((a/b)\%p^{[1]})，然而不同于加减乘，除法取模没有((a/b)\%p=(a\%p/b\%p)\%p)的性质。因此，我们引入乘法逆元的概念。
若(a* b≡1(\%p))，则设(b=inv(a))，称(b)是(a)的逆元，满足((a*b)\%p=(a\%p*b\%p)\%p)。这样，除法转换为乘法，就可以了。
所有的有理数都有一个与其对应的逆元。因此，对于两个整数(A,B)，要计算(frac{A}{B})（实数除法）时，(A)不一定要被(B)整除。
对于两个取模过的数，逆元是怎么输出商的？它实际上是在对给定的取模过的数(a,b)，找最小的两个(A,B)，满足(A=x* p+a,B=y* p+b,A\%B=0)，并返回(A/B)。
求逆元的几种常用方法
1. 扩展欧几里得
欧几里得定理
想必都知道$$gcd(a,b)=gcd(b,a%b)$$
解关于(x,y)的方程(ax+by=gcd(a,b))
首先，我们先解出方程的一个特解，再通过特解推出其余的通解即可。
如何求特解
我们来看下面两个方程：
(ecause gcd(a,b)=gcd(b,a\%b),)
( herefore ax_1+by_1=bx_2+(a\%b)y_2)
(ecause a\%b=a-floor(a/b)* b^{[2]})
( herefore ax_1+by_1=ay_2+b(x_2-floor(a/b)* y_2))
由等式两边的系数关系得$$x_1=y_2$$$$y_1=x_2-floor(a/b)* y_2$$
于是形成了一种递归关系，可用递归解决。
递归终止状态
我们知道在计算最大公约数的过程中，(b)最终会等于(0)，此时(a=gcd(A,B))，因此，这时方程化为(a* x=gcd(A,B))，解得(x=1,y=0)。
如何求通解
求得一组特解之后，我们发现，对于方程(ax+by=gcd(a,b))，当(x)增加(b/gcd)，(y)减少(a/gcd)时，等式仍成立。
证明
(ax)项增加(a* b/gcd)，(by)项减少(a* b/gcd)。
于是可求得所有通解。
如何求最小非负整数解
此处以(x)为例，(y)同理。我们让(x)一直减(B/gcd)直至求出最小解，即让(x\%(B/gcd))即可。
解关于(x,y)的方程(Ax+By=C)
我们发现，当(C)不能整除(gcd(A,B))时，方程就不能化为(ax+by=gcd(a,b))的形式，因此就无解。否则有无数解，将方程两边同时除以(frac{C}{gcd(A,B)})求解即可。
Code
typedef long long D;
D egcd(D a,D b,D &x,D &y){
if(b==0){
x=1;
y=0;
return a;
}
D ans=egcd(b,a%b,x,y),tmp=x;
x=y;
y=tmp-a/b*y;
return ans;
}
D cal(D a,D b,D c){
D x,y,g=egcd(a,b,x,y);
if(c%g!=0)return -1;
b=abs(b/g);
x=(x*(c/g)%b+b)%b;
return x;
}
利用扩展欧几里得求乘法逆元
因为$$a* x≡1(%p)$$
所以$$a* x+b* y=1$$
此时，若(1\%gcd(a,b)≠1)，即(gcd(a,b)≠1)，则该方程无解。
否则，设特解为(x_0)，最小非负整数解(x=x_0\%m)。当(m<0)时，由于计算机取模一个负数与数学上的意义不同，所以应把模数取绝对值。当(x_0<0)时，取模的结果是一个负数，所以把答案加上(m)即可。
复杂度为(log)级。
Code
typedef long long D;
D egcd(D a,D b,D &x,D &y){
if(b==0){
x=1;
y=0;
return a;
}
D ans=egcd(b,a%b,x,y),tmp=x;
x=y;
y=tmp-a/b*y;
return ans;
}
D cal(D a,D m){
D x,y,g=egcd(a,m,x,y);
if(g!=1)return -1;
m=abs(m/g);
x=(x%m+m)%m;
return x;
}
2. 利用费马小定理
当(p)为质数时， (a^{p-1}≡1(\%p)) ，对(a* x≡1(\%p))有(x=a^{p-2}\%p)。
复杂度为(log)级。
Code
typedef long long D;
D qpow(D x,D y,D p){
D ans=1;
while(y){
if(y&1)ans=ans*x%p;
x=x*x%p;
y>>=1;
}
return ans;
}
D cal(D a,D p){
return qpow(a,p-2,p);
}
组合数取模(Lucas 定理)
由于题目中给的(p)一般都是质数，所以下面我们默认(p)为质数。
1. 错误方法
由上面的结论，我们得出$$C(n,m)=frac{n!}{m!(n-m)!}=n!* inv(m!)* inv((n-m)!)$$
直接使用扩展欧几里得或费马小定理求逆元来实现除法取模。
此方法的错误之处在于，对(a* x≡1(\%p),a)有逆元的前提条件时(a,p)互质。当(a,p)不互质，即(a)是(p)的倍数时，不存在逆元，也就无法计算。
比如计算(C(7,5)\%5)，正确答案应该是(frac{7* 6}{1* 2}\%5=21\%5=1)，但计算过程中出现了(5)的倍数，取模(5)之后就变为(0)，因此最后答案输出了(0)。
2. Lucas定理
lucas定理可避免上述情况。
递归式：
设(lucas(n,m,p))为(C(n,m)\%p) （(p)为质数），则
此处的(C(n,m,p))可直接通过逆元计算。
复杂度为(log)级。
证明
Code
typedef long long D;
D fac[100001];
void preparefac(D n,D p){
fac[0]=1;
for(D i=1;i<=n;i++){
fac[i]=i*fac[i-1]%p;
}
}
D qpow(D x,D y,D p){
D ans=1;
while(y>0){
if(y%2)ans=ans*x%p;
x=x*x%p;
y/=2;
}
return ans;
}
D cal(D x,D y){
return qpow(x,y-2,y);
}
D Div(D x,D y,D p){
return x*cal(y,p)%p;
}
D C_(D n,D m,D p){
if(m>n)return 0;
return Div(Div(fac[n],fac[m],p),fac[n-m],p);
}
D C(D n,D m,D p){
if(!m)return 1;
return C_(n%p,m%p,p)*C(n/p,m/p,p)%p;
}
线性递推求逆元
首先 (1^{-1}≡1(\%p))
设 (p=k* i+r)
则 (k* i+r≡0(\%p))
等式两边乘 (i^{-1}* r^{-1})
得 (k* r^{-1}+i^{-1}≡0(\%p))
( herefore i^{-1}≡-k* r^{-1}(\%p))
( herefore i^{-1}≡-floor(frac{p}{i})* (p\%i)^{-1}(\%p))
Code
inv[1]=1;
inv[i]=(p-p/i)*inv[p%i]%p;
阶乘逆元
(i) 的阶乘逆元等于 (i-1) 的阶乘逆元乘以 (i) 的逆元。
Code
facinv[i]=facinv[i-1]*inv[i]%p;
CRT
用于求解一元线性同余方程组 (xequiv a_ipmod{m_i})。
过程：
- (b_i=prod_{j eq i}m_j)
- (c_iequiv b_i^{-1}pmod{m_i})
- (ans=sum_{i=1}^n a_ib_ic_ipmod{prod_i m_i})
证明
对于(iin[1,n])，(ansequiv a_i+sum_{j eq i} a_jb_jc_jpmod{m_i})，由于(m_i|b_j(j eq i))，( herefore ansequiv a_ipmod{m_i})
exCRT
对于多个方程的情况，考虑将方程两两合并。
对于两个方程的情况(xequiv a_1pmod{m_1},xequiv a_2pmod{m_2})
转换：(x=m_1s+a_1=m_2t+a_2 Rightarrow m_1s-m_2t=a_2-a_1)，使用exgcd求解
当(gcd(m_1,m_2) mid a_2-a_1)时无解
高端数论
积性函数
(f(xy)=f(x)f(y)(xperp y))
完全积性函数
(f(xy)=f(x)f(y))
欧拉函数
定义
(varphi(n)=sum_{i=1}^n [iperp n])
性质
显然，除了它本身以外的数都和该质数互质。
与 (p^k) 不互质的数就是 (p) 的倍数，有 (frac{p^k}{p}=p^{k-1}) 个。
设 (S_x={) 所有与 (x) 互质且 (le x) 的数 (}) 。显然 (|S_x|=varphi(x)) 。
(ecause gcd(a,b)=1,)
( herefore S_{a*b}) 与 (S_a,S_b) 一一对应。
( herefore |S_{a*b}|=|S_a|*|S_b|,) 即 (varphi(a*b)=varphi(a)*varphi(b))
(varphi(2)=1) ，易证。
(varphi(frac{n}{p})=frac{n}{p}*prod (1-frac{1}{p_i}))
(varphi(n)=p*frac{n}{p}*prod (1-frac{1}{p_i})=p*varphi(frac{n}{p}))
(varphi(p)=p-1) ，易证。
设 (f(n)=sum_{d|n}varphi(d))
当 (gcd(x,y)=1) 时， (f(x)*f(y)=xprod_{p_i是x的质因子}(1-frac{1}{p_i})*yprod_{p_i是y的质因子}(1-frac{1}{p_i})=x*yprod_{p_i是x*y的质因子}(1-frac{1}{p_i})=f(x*y))
( herefore f(n)) 是积性函数。
(f(p^k)=sum_{i=0}^k varphi(p^i)=p^k)
于是我们把 (n) 分解质因数：
(n=prod p_i^{k_i})
(f(n)=prod f(p_i^{k_i})=prod p_i^{k_i}=n)
公式
(varphi(x)=xprod (1-frac{1}{p_i}))
(p_i) 为 (x) 的第 (i) 个质因子， (x≥2) 。 (varphi(1)=1) 。
根据唯一分解定理， (x=prod p_i^{k_i}) 。
( herefore varphi(x)=prod varphi(p_i^{k_i})=prod (p_i^{k_i}-p_i^{k_i-1})=xprod (1-frac{1}{p_i}))
其他常用函数
(epsilon(n)=[n=1])
(id(n)=n)
(1(n)=1)
(sigma_k(n)=sum_{dmid n}d^k)
其中(omega(n))表示(n)的本质不同质因子个数，是一个积性函数。
狄利克雷卷积
((f*g)(n)=sum_{dmid n}f(d)g(frac{n}{d}))
例子
(varphi=mu*id)证明
(varphi*1=id Rightarrow varphi*1*mu=id*mu Rightarrow varphi*epsilon=mu*id)
莫比乌斯反演
(f(n)=sum_{dmid n}g(d)Rightarrow g(n)=sum_{dmid n}mu(d)f(frac{n}{d}))