求模的逆元

2019-04-13 12:14发布

站内文章 / 模拟电子
9295 0 1208
欧拉函数Φ(n) 一些定理： •欧拉定理 –a和n都是正整数，且a和n互素，则aΦ(n) ≡ 1 (mod n) •ab (mod n) = a(b % Φ(n) + Φ(n)) (mod n) •ab (mod n) = a(b % Φ(n))(mod n),gcd(a,n)=1

 •费马小定理(欧拉定理弱化形式) –设a是正整数，p是素数，且a和p互素,则pow(a,p-1) ≡ 1 (mod p)(因为Φ(p)=p-1)

 逆元 •若a*b=1（modm）则称作b是a在模m下的逆元。记作a^-1=b(mod m) •显然只有(a,m)=1时存在逆元。 •性质： a^-1=b(mod m)时 •b^-1=a(mod m) •a*b=1(mod m) •a^-1=b+km(mod m) •m/a=m*b(mod m)

求逆元

 •1.a*x+b*y=1;解方程得x为a在mod b下的逆元。(要求gcd(a,b)=1)（exgcd方法）
#include #include using namespace std; int x,y,d,a,b;//a*x + b*y=GCD(a,b) //d为答案 void exgcd(int a, int b, int &d, int &x, int &y) { if(!b){d=a;x=1;y=0;} else {exgcd(b, a%b, d, y, x); y-=x*(a/b);} } int main() { scanf("%d%d",&a,&b); exgcd(a,b,d,x,y); printf("x=%d y=%d d=%d ",x,y,d); return 0; }

•2.a^(Φ(m) -1)=b;注意gcd(a,m)=1;特别地，当p为素数时，a^(p-2)=b;
（快速幂）
LL po(LL k) {     LL ret=1;     LL m=MOD-2;     while(m)     {         if(m&1LL)ret=ret*k%MOD;         k=k*k%MOD;         m>>=1LL;     }     return ret; }



热门文章