2020.1.29
数论（二）
1.线性组合
给定整数{x~1~,x~2~,x~3~,...,x~n~}和k
求任意一组整数{a~1~,a~2~,a~3~,...,a~n~}
满足a~1~x~1~+a~2~x~2~+a~3~x~3~+...+a~n~x~n~=k，或返回无解。
解法
设d=gcd(x~1~,x~2~,...,x~n~)显然仅当d|k时有解（k可以看成n组d的和）
若n=1则直接令a~1~= k/x~1~。（只有一个数）
否则用gcd(x~n−1~,x~n~)代替x~n-1~和x~n~，递归构造解；(将两个数合并成一个)
回溯时调用exgcd(x~n−1~,x~n~),求出相应的a~n-1~,a~n~,使a~n-1~x~n-1~+a~n~x~n~=gcd(x~n-1~,x~n~)
用x~n−1~,x~n~的线性组合替代 (x~n−1~, x~n~)。
2.逆元
若ax≡1(mod b)，则称x是a关于模b的逆元，常记做a^−1^。(和a的倒数不同！这里指只要符合ax%b=1就可，也就是说ax的值可以是：1，b+1，···，yb+1（y为任意整数）)
上式等价于ax+by=1（ax，by异号）
因此逆元不一定存在，存在的充要条件为gcd(a,b)=1（a，b互质，若不互质，a模b余数一定整除gcd(a,b)）
推论：如果p是质数，且p不整除a（互质），则a模p的逆元存在。
证明：[0,b)的范围内，a关于模b的逆元(整数)(若存在)是唯一的。
定义式可化为：ax%b=1，在这个式子中，x=0和x=b是等价的
反证法，若a有两个逆元0<x~1~<x~2~<b
即ax~1~≡ax~2~≡1(mod b)(两积同余1)
那么有b|a(x~2~−x~1~)成立(余数相减抵消，故：b|(ax~2~-ax~1~))，与0<x~2~−x~1~<b矛盾
求逆元
1.exgcd
因为gcd(a,b)=1
所以exgcd求的ax+by=gcd(a,b)就是ax+by=1
2.递推
假设现在要求i mod 质数p的逆元
考虑带余除法，设p=iq+r，q=p/i，r=p%i
则有iq+r≡0(mod p)（二者相等，商0余0）
注意到p是质数，因此r不为0（若r为0，则p有除1和本身以外的因数，故r不为0），r的逆元存在(gcd(r,p)=1,任何非零数和质数互质)
iq+r≡0(mod p)两边乘i^−1^r^−1^，（这里^-1^不是倒数，是逆元！i·i^-1^%p=1，r·r^-1^%p=1）因为i·i^-1^=yp+1,r·r^-1^=y~0~p+1，所以：
原式 –> qr^-1^(yp+1)+i^-1^(y~0~p+1)≡0(mod p) –> qr^-1^yp+qr^-1^+i^-1^y~0~p+i^-1^≡0(mod p) –> qr^-1^+r≡0(mod p) （将多项式中带有p的项消掉了）
推得式子：qr^−1^+i^−1^≡0(mod p) –> qr^−1^+i^-1^=i^-1^-(-qr^-1^)
易证：若a+b%c=0，那么a≡-1b(mod c)，q=p/i,r=p%i
因此i^−1^≡−qr^−1^≡−(p/i)(p%i)^−1^(mod p) –> i^-1^%p=−qr^−1^%p –> i^-1^=kr^-1^-qr^-1^%p(k为正整数，保证kr^-1^和qr^-1^的差大于0)
因为r·r^-1^=yp+1,所以r^-1^=(yp+1)/r,
代码
for(inv[1]=1,i=2;i<=n;i++)//1%任何大于1的数都是1，所以inv[1]=1
inv[i]=(p-q)*inv[r]%p;//这里的k取p，因为q永远不会比p大，所以p作k足矣
3.倒推
先用方法1（exgcd）求n!的逆元(注：这里所有bulabula^-1^都是逆元，不是倒数)
推导：((k-1)!·((k-1)!)^-1^)%p=1 –> ((k-1)!)^-1^·(k-1)!=xp+1 –> ((k-1)!)^-1^=(xp+1)/(k-1)! (x和下面的y是正整数，x=(((k-1)!)^-1^·(k-1)!)/p),y=(k!·(k!)^-1^)/p)
同理：(k!)^-1^=(yp+1)/k! –> k·(k!)^-1^=(yp+1)/(k-1)!
因为：xp+1≡yp+1(mod p)(同余1)
所以：(xp+1)/(k-1)!≡(yp+1)/(k-1)!(mod p)（在整除的情况下成立，并且由于xp+1,yp+1本就是乘出来的，所以保证了整除）
可得：((k−1)!)^−1^≡k·(k!)^−1^(mod p)
最后：((k-1)!)^-1^=k·(k!)^-1^%p（逆元永远大于0小于取模的p,所以可以求得唯一的逆元）
这样就可以倒推求出1!~(n − 1)!的逆元
因为要求k的逆元，所以继续推导：
根据定义：k·k^-1^=xp+1(x为正整数，x=(k·k^-1^)/p)
推得：k^-1^=(xp+1)/k
同理：(k!)^-1^=(yp+1)/k!
等式两边同乘(k-1)!：(k-1)!·(k!)^-1^=(yp+1)/k
因为：(xp+1)%p=1,(yp+1)%p=1
所以：(xp+1)/k≡(yp+1)/k(mod p)
也就是：k^−1^≡(k−1)!·(k!)^−1^(mod p)
最后：k^-1^=((k−1)!·(k!)^−1^)%p
就可以求出1~n的逆元了
例题：组合数取模
求C(n, k)%998244353(一个质数)
T≤105,0≤k≤n≤107
公式：
要求：O(1)回答询问
线性求逆，预处理n!以及n!的逆元
那么C~n,k~=n!·(k!)^-1^·((n-k)!)^-1^ (因为要取模，所以除以一个数就相当于乘这个数和取模数的逆元)
3.线性同余方程
形如ax≡c(mod b)的方程，称为线性同余方程。
等价于ax+by=c（x,y有正有负）因此有解条件为gcd(a,b)|c
若(a,b)=1，则x有唯一解x≡a^−1^·c(mod b)（逆元不是倒数）
推导：易证c和c%b在方程中等价，所以使c=c%b
设整数k=(a·a^-1^)/b，所以a·a^-1^=kb+1
所以：c·a·a^-1^=k·b·c+c
整理得：c·a·a^-1^-b·k·c=c
很显然，在ax+by=c方程中，x=c·a^-1^,y=-k·c（我们不关心y是多少）
当然，a^-1^·c是可以大于b的，所以要求x,要给a^-1^·c取模
a,b不互质的情况：
设gcd(a,b)=d a=a′d b=b′d c=c′d
（这时a,b不互质，加上之前交代的有解条件gcd(a,b)|c，所以d=gcd(a,b,c)）
所以a′,b′互质，按照互质的情况求出a′x+b′y=c′的解，因为等式两边同除以d，所以在这里求出的x,y在原方程仍然适用
线性同余方程组
考虑形如 x ≡ ai(mod mi) 的若干方程联立得到的方程组，如：
x≡2(mod 3) (1)
x≡3(mod 5) (2)
x≡5(mod 7) (3)
解法：
设x=3y+2,代入(2)
3y+2≡3(mod 5) –> 3y≡1(mod 5)
gcd(3,5)=1
3^-1^(mod 5)=2
由线性同余方程解法可得：y≡2*1(mod 5)
解得y≡2(mod 5)
设y=5z+2,代入(3)
3(5z+2)+2≡5(mod 7) –> 15z+6+2≡5(mod 7) –> 15z+8≡5(mod 7) –> 15z≡-3(mod 7) –> 15z≡4(mod 7)
gcd(15,7)=1
15^-1^(mod)=1
由线性同余方程解法可得：z=4*1(mod 7)
解得z≡4(mod 7)（z%7=4）
设z=7k+4,带回y=5z+2
y=5(7k+4)+2=35k+20+2=35k+22
带回x=3y+2
x=3(35k+22)+2=105k+68
x%105=68
也就是：x≡68(mod 105)
中国剩余定理
对于同余方程组x≡a~i~(mod m~i~)(i=1~n)
设M=m~1~m~2~...m~n~，M~i~=M/m~i~
若m~i~两两互质，则x在mod M下有唯一解。
中国剩余定理同时也给出了构造解的方法：
因为m~i~两两互质，所以m~i~的质因数在M~i~中不出现，所以gcd(M~i~,m~i~)=1，所以M~i~关于模m~i~的逆元存在。（逆元定义）
把这个逆元设为t~i~，于是有：
M~i~t~i~≡1(mod m~i~)
设正整数j/=i
因为m~j~是M~i~的因子，所以M~i~%m~j~=0
因为t~i~是整数，所以：M~i~t~i~%m~j~=0
前面有：M~i~t~i~≡1(mod m~i~)
等式两边同时乘a~i~，得：a~i~M~i~t~i~≡a~i~(mod m~i~)
同理：a~i~M~i~t~i~≡0(mod m~j~)
所以每个(a~i~M~i~t~i~)只对自己对应的m~i~取模时有余数，对其他m~j~取模答案都为0，这样一来，如果把所有(a~i~M~i~t~i~)都加起来，用这个和对M取模后的余数只有a~i~，满足i取任意正整数时，x≡a~i~(mod m~i~)的要求，也就解出了方程组
因此解为x≡a~1~M~1~t~1~+a~2~M~2~t~2~+...+a~n~M~n~t~n~(mod M)
代码：
int crt(int a[],int m[],int n) {//不是递归
int M=1,ret=0;//ret就是x的解的余数部分（模数部分就是M）
for(int i=1;i<=n;i++)
M*=m[i];//累乘M
for(int i=1;i<=n;i++) {
int Mi=M/m[i],ti=inv(Mi,m[i]);//Mi随用随算，逆元函数提前写好
ret=(ret+a[i]*Mi*ti)%M;//累乘处理ret
}
return ret;
}