一.逆元
概念和作用:
逆元其实跟倒数很相似。
逆元概念:方程 ax≡1(mod p )的解称为 a 关于模 p 的逆,当 gcd(a,p)=1(即 a,p 互质)时,方程有唯一解,否则无解。
逆元的作用:对于求(a/b)mod p,直接除会爆精度,此时就可以采用逆元(a∗inv(b)) mod p.
求法:
1、费马小定律
当 p 为质数时,有 ap−1≡ 1 (mod p) ,那么易得出 a ∗ a p − 2 ≡ 1 ( m o d p )
a p−2就是 a 关于模 p 的逆元
直接用快速幂即可算出答案,quickpow(b, p−2).
2、扩展欧几里得算法
求 ax ≡ 1 (mod) p 的一个解,用Exgcd求解即可解决,a、p互质
Code:
void Exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) x=1,y=0;
else Exgcd(b,a%b,y,x),y-=a/b*x;
}
int NY(int a,int p){
ll x,y;
Exgcd(a,p,x,y);
return (x%p+p)%p;
}
3、递推
多个连续的乘法逆元,可以采用递推求解
令p = ki + r ( 0 <= r < i ) ,于是得到ki + r ≡ 0 ( m o d p ),等式两边同时乘上i − 1 , r − 1得到kr − 1 + i − 1 ≡ 0 ( m o d p ) ,移项可得i − 1 ≡ − ⌊ p / i ⌋ ∗ ( p m o d i ) − 1 ( m o d p )
通常写成:
i n v [ i ] = ( ( p − p / i ) ∗ i n v [ p % i ] + p ) % p
Code:
int inv[N];
void get_inverse(int n,int p)
{
int i;
inv[1]=1;
for(i=2;i<=n;++i)
inv[i]=(p-p/i)*inv[p%i]%p;
注:
对于Fibonacci Sum题中,求阶乘逆元有两种方法
Code1:
先用递推求得每一位的逆元,再计算阶乘
finv[1] = 1;
for( int i = 2; i <=n; i++ ) finv[i] = ( P - P / i ) * finv[ P % i ] % P;
finv[0]=1;
for(int i=1;i<=n;i++) finv[i]=finv[i]*finv[i-1]%P;
Code2
利用公式1 / ( n + 1 ) ! × ( n + 1 ) = 1 / n ! ,求得1 / n !后倒推回去
finv[n]=fp(fac[n],P-2); //这里是用的快速幂和费马小定律算的1/n!的值
for(int i=n-1;i>=0;i--) finv[i]=finv[i+1]*(i+1)%P;
二.欧拉降幂公式
a
b
≡
a b % φ ( p ) ( m o d p ) a^{b\%φ(p)}\, \:\, \:\, \:\, \:\, \:\, \:\, \:(mod\, \: p)a
b%φ(p)
(modp) \, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \: n , a 互 质 n,a互质n,a互质
a b ( m o d p ) a^ b \, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \, \:\, \:\, \:\, \:\:(mod\, \: p)a
b
(modp) \, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \: b < φ ( n ) b<φ(n)b<φ(n)
a b % φ ( n ) + φ ( n ) ( m o d p ) a ^{b\%φ(n)+φ(n)}\, \:\, \:(mod\, \: p)a
b%φ(n)+φ(n)
(modp) \, \:\, \:\, \:\, \:\, \:\, \:\, \:\, \: b ≥ φ ( n ) b≥φ(n)b≥φ(n)
其中φ(n)表示小于等于m的数中与n互质的数的数目
φ(即phi)是欧拉函数
求解欧拉函数代码:
ll euler_phi(ll n) {
ll k = (ll)sqrt(n + 0.5);
ll ans = n;
for(int i = 2; i <= k; i++) {
if(n % i == 0) {
ans = ans / i * (i - 1);
while(n % i == 0) n /= i;
}
}
if(n > 1) ans = ans / n * (n - 1);
return ans;
}
三.二次剩余
概念:
当存在某个X,式子x2 ≡ n ( m o d p )成立时,称“n是模p的二次剩余”
当对任意不成立时,称“ n是模 p的二次非剩余”
作用:
对于一个数n,求根号下n对p取模的时候,可以看n是否是模p的二次剩余,是的话可以用x去代替根号n
Code:
#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
const int mod=1e9 + 9;
typedef long long ll;
template<typename T>
inline int pow(int x,T y)
{
int res=1;x%=mod;
for(;y;y>>=1,x=(ll)x*x%mod) if(y&1) res=(ll)res*x%mod;
return res;
}
inline int Quadratic_residue(const int a)
{
if(a==0)return 0;
int b=(rand()<<14^rand())%mod;
while(pow(b,(mod-1)>>1)!=mod-1)b=(rand()<<14^rand())%mod;
int s=mod-1,t=0,x,inv=pow(a,mod-2),f=1;
while(!(s&1))s>>=1,t++,f<<=1;
t--,x=pow(a,(s+1)>>1),f>>=1;
while(t)
{
f>>=1;
if(pow((int)((ll)inv*x%mod*x%mod),f)!=1) x=(ll)x*pow(b,s)%mod;
t--,s<<=1;
}
return min(x,mod-x);
}
int main(){
int n;
scanf("%d", &n);
printf("%d\n", Quadratic_residue(n));
return 0;
}
Comments | NOTHING