同余
加法同余
(a + b) % p = (a % p + b % p) % p
乘法同余
a * b % p = (a % p)*(b % p) % p
减法同余
(a - b) % p = (a % p - b % p + p ) % p
线性同余方程
-
求x使得 ax = b (mod p)
-
等价于求 ax + py = b 的一个解 x
除法同余与逆元
计算 a / b % p
若 b * x % p == 1 即 gcd(b,p) == 1
则称 x 为 b 在（mod p） 意义下的逆元
a / b % p = (a % p * x % p ) % p
下面是一些逆元的求法
费马小定理
- 使用条件 p 为质数
则 b 在 (mod p) 意义下的逆元为 b ^ (p-2)
typedef long long ll;
ll qpow(ll b,ll e,ll p){ll ans=1;b%=p;while(e){if(e&1)ans=ans*b%p;e>>=1;b=b*b%p;}return ans;
}
int inv(int b,int p){return qpow(b,p-2,p);
}
拓展欧几里得
- 使用条件 a , b互质
int ex_gcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return a;}int g=ex_gcd(b,a%b,y,x);y-=a/b*x;return g;
}
int inv(int b,int p){int x,y;ex_gcd(b,p,x,y);return (x%p+p)%p;
}
线性求连续数字逆元
const int N=1e8+5;int inv[N];
void built(int n,int p){inv[1]=1;for(int i=2;i<=n;++i){inv[i]=1LL*(p-p/i)*inv[p%i]%p;}
}
线性求阶乘逆元
const int N=1e5+5;ll qpow(ll b,ll e,ll p){ll ans=1;b%=p;while(e){if(e&1)ans=ans*b%p;e>>=1;b=b*b%p;}return ans;
}int f[N];//f[i]表示i!在(mod p)意义下的余数
int inv[N];//inv[i]表示i！在(mod p)意义下的逆元void built(int n,int p){f[1]=1;for(int i=2;i<=n;++i){f[i]=1LL*i*f[i-1]%p;}inv[n]=qpow(f[n],p-2,p);for(int i=n;i;--i){inv[i-1]=1LL*i*inv[i]%p;}
}
//（mod p）意义下的组合数
int C(int n,int m,int p){// n! / m! / (n-m)!int ans=f[n];ans=ans*inv[m]%p;ans=ans*inv[n-m]%p;return ans;
}