逆元学习笔记

定义

若在mod p意义下，对于一个整数a，有a*b≡1(mod p)，那么这个整数b即为a的 乘法逆元，同时a也为b的乘法逆元， 一个数有逆元的充分必要条件是gcd(a,p)=1，此时a才有对p的乘法逆元

运用

主要是用于取模。

模板

费马小定理

long long qkpow(long long x,long long y,long long p){ long long ans=1; while(y){ if(y&1) ans=ans*x%p; x=x*x%p; y>>=1; } return ans; } long long inv(long long x,long long p){ return qkpow(x,p-2,p); }

拓展欧几里德

void exgcd(long long a,long long b,long long &x,long long &y){ if(!b) x=1,y=0; else{ exgcd(b,a%b,y,x); y-=x*(a/b); } } long long inv(long long a,long long b){ long long x,y; exgcd(a,b,x,y); return (x+b)%b; }

递推

f[1]=1; for(int i=2;i<=n;i++){ f[i]=(-f[p%i]*(p/i)%p+p)%p; }