-
(gcd)：
inline int gcd(int a,int b){ return b?gcd(b,a%b):a;} -
扩展欧几里得：求(ax+by=gcd(a,b))的一组整数解。
inline int Exgcd(int a,int b,int &x,int &y) { if(!b) {x=1,y=0;return a;} int Gcd=Exgcd(b,a%b,y,x); y-=a/b*x;return Gcd; } -
费马小定理：(a^{p-1}equiv 1mod p)（(p)为质数）
-
欧拉定理（(gcd(a,n) e 1)）：（無駄？）
[a^bequiv left{egin{array}{ll} a^b & b<varphi(n)\a^{bmodvarphi(n)+varphi(n)} & bgeq varphi(n)end{array} ight.mod n ] -
欧拉定理（(gcd(a,n)=1)）：(a^{varphi(n)}equiv 1mod n)（無駄？）
-
中国剩余定理（孙子定理）：(p_1,p_2,p_3...p_k)两两互质，求一下方程组的最小整数解
[left{egin{array}{ll}xequiv a_1mod p_1\xequiv a_2mod p_2\...\xequiv a_kmod p_kend{array} ight. ]令(P=prod p_i)，(P_i=frac{P}{p_i})，(t_i,P_i)满足(t_iP_iequiv1mod p_i)。
所以最小整数解为：(x=sum a_iP_it_i mod P)。
inline int Exgcd(int a,int b,int &x,int &y) { if(!b) {x=1,y=0;return a;} int Gcd=Exgcd(b,a%b,y,x); y-=a/b*x;return Gcd; } int main(){ n=read(); for(int i=1;i<=n;i++) p[i]=read(),a[i]=read(),P*=p[i]; for(int i=1;i<=n;i++) { int Pi=P/p[i],x,y;Exgcd(Pi,p[i],x,y); ans=(ans+a[i]*Pi*((x%p[i]+p[i])%p[i]))%P; } printf("%lld",ans); } -
扩展中国剩余定理（
儿子定理）(p_1,p_2,p_3...p_k)不一定两两互质，求一下方程组的最小整数解[left{egin{array}{ll}xequiv a_1mod p_1\xequiv a_2mod p_2\...\xequiv a_kmod p_kend{array} ight. ]考虑两个式子：(xequiv a_1 mod p_1,xequiv a_2mod p_2)合并（这里是完整的推导过程）注意不同部分的模数因为其来源可能不同
可以合并成：(xequiv a'mod m')。其中(a'=p_1[inv(frac{p_1}{gcd},frac{p_2}{gcd})frac{a_2-a_1}{gcd}\%frac{p_2}{gcd}]+a_1,m'=frac{p_1p_2}{gcd})（(gcd=gcd(p_1,p_2),inv(x,y))表示(x)在模(y)意义下的逆元，(y)不一定为质数，所以要用(Exgcd)求）
inline int gcd(int x,int b) {return b?gcd(b,x%b):x;} inline int Exgcd(int a,int b,int &x,int &y) { if(!b) {x=1,y=0;return a;} int Gcd=Exgcd(b,a%b,y,x); y-=a/b*x;return Gcd; } inline int Inv(int a,int b){int x,y;Exgcd(a,b,x,y);return (x%b+b)%b;} signed main(){ int Jud=0;n=read(); for(int i=1;i<=n;i++) p[i]=read(),a[i]=read(); for(int i=2;i<=n;i++) { int Gcd=gcd(p[i],p[i-1]),Now,p1=p[i-1],p2=p[i],a1=a[i-1],a2=a[i]; Now=Inv(p1/Gcd,p2/Gcd)%(p2/Gcd); Now=(Now*(((a2-a1)/Gcd)%(p2/Gcd))%(p2/Gcd)+(p2/Gcd))%(p2/Gcd); Now=((Now%(p2*p1/Gcd)*p1%(p2*p1/Gcd))%(p2*p1/Gcd)+(p2*p1/Gcd))%(p2*p1/Gcd); Now=(Now%(p2*p1/Gcd)+a1%(p2*p1/Gcd))%(p2*p1/Gcd); p[i]=p2*p1/gcd(p2,p1); a[i]=(Now%p[i]+p[i])%p[i]; } print(Jud?-1:a[n]); } -
(BSGS)：求(A^xequiv Bmod C)的(x)。（满足(gcd(A,C)=1)）
设(m=sqrt{C})，令(x=am+b)，所以有(A^{am}equiv A^bBmod C)，预处理(A^b)，暴力枚举(a)即可。
int m=sqrt(C)+1,now=1; for(int i=0;i<m;i++)mp[(now*B)%C]=i,now=((now%C)*(A%C))%C; k=((k%C)*(now%C))%C; for(int i=1;i<=m;i++) { if(mp[k]) return ((i%C)*(m%C)-mp[k]+C)%C; k=((k%C)*(now%C))%C; } -
扩展(BSGS)：求(A^xequiv Bmod C)的(x)。（不一定满足(gcd(A,C)=1)）
令(d=gcd(A,C))，则我们可以除掉(d)，原始变为(frac{A}{d}A^{x-1}equiv frac{B}{d}mod frac{C}{d})，不断检查(gcd(frac{z}{d},y))，一直除到互质为止，最后将减掉的补回来就行了。
inline int EXBSGS(int A,int B,int C) { int cnt=0,d,k=1; while((d=gcd(A,C))^1) { if(B%d) return -1; B/=d;C/=d;++cnt; k=(k*(A/d))%C; if(k==B) return cnt; } mp.clear();int m=sqrt(C)+1,now=1; for(int i=0;i<m;i++) mp[(now*B)%C]=i，now=(now*A)%C; k=(k*now)%C; for(int i=1;i<=m;i++) { if(mp[k]) return (cnt+i*m-mp[k]+C)%C; k=(k*now)%C; } return -1; } -
线性筛：（不多讲，直接上）
inline void Make_Prime(int T) { Vis[1]=1; for(int i=2;i<=T;i++) { if(!Vis[i]) Pri[++Cnt]=i; for(int j=1;j<=Cnt&&i*Pri[j]<=T;j++) { Vis[i*Pri[j]]=1; if(!(i%Pri[j])) break; } } } -
(Miller) (Rabin)：
前置定理：费马小定理，二次探测：若(a^2equiv 1mod p)且(p)为质数，则(aequiv1)或(p-1mod p)。
假设我们判定(x)，将其拆为(x=2^kt)形式，随即一个(a)并求出(a^t)，然后依次将(2)乘上去，用二次探测即可。
最好我们多测几次(Miller) (Rabin)。
int Tex[4]={2,3,5,7}; inline int ksm(int b,int k,int p) { int a=b; k--; while(k) { if(k&1) a=(a%p*b%p+p)%p; b=(b%p*b%p+p)%p;k>>=1; } return a%p; } inline bool Miller_Rabin(int x) { if(x==1) return 0; int Now=x-1,k=0; while(!(Now&1)) Now>>=1,k++; for(int i=0;i<4;i++) { int a=ksm(Tex[i],Now,x)%x,Nex=a; if(x==Tex[i]) return 1; for(int j=1;j<=k;j++) { Nex=(a%x*a%x+x)%x; if(Nex==1&&a!=1&&a!=x-1) return 0; a=Nex; } if(a!=1) return 0; } return 1; } -
(Lucas)：懒得证明了，记着：({n choose m}\%p={n\%p choose m\%p}*{n/p choose m/p}\%p)
inline int ksm(int b,int k) { int a=b;k--; while(k) { if(k&1) a=(a%p*b%p)%p; b=(b%p*b%p)%p;k>>=1; } return a%p; } inline int C(int n,int m) { if(m>n) return 0; return (Fac[n]%p*ksm((Fac[m]%p*Fac[n-m]%p)%p,p-2)%p)%p; } inline int Lucas(int n,int m) { if(!m) return 1; return (C(n%p,m%p)%p*Lucas(n/p,m/p)%p)%p; }