逆元小结

2019-04-14 12:09发布

站内文章 / 模拟电子
11239 0 1486
一、若a与n互素,那么可以用扩展欧几里德和欧拉函数求出a对于n的逆元。 ax≡1(mod n),x为a对于n的逆元。 直接用欧几里德求逆元x： //a与n互素,逆元才有解 #include #include using namespace std; typedef long long LL; void exgcd(LL a,LL b,LL &d,LL &x,LL &y) { if(!b) { d=a;x=1;y=0; return ; } exgcd(b,a%b,d,y,x); y-=x*(a/b); } LL inv(LL a,LL n) { LL d,x,y; exgcd(a,n,d,x,y); return d==1?(x+n)%n:-1; } int main() { cout< 欧拉定理：对于任何两个互质的正整数a，n(n>=2)，有a^(φ(n))≡1(mod n)。 那么只要a与n互质,逆元x=a^(φ(n)-1)%n,可以用快速幂求出。 用欧拉定理求解逆元x: LL inv(LL a,LL euler,LL n) { LL ret=1; --euler; while(euler) { if(euler&1) ret=ret*a%n; euler>>=1; a=a*a%n; } return ret; }
特殊地,若n是素数的话可以用费马小定理求解。 费马小定理：当n是素数时,a^(n-1)≡1(mod n)。（费马小定理是欧拉定理的特殊情况）
 那么逆元x=a^(n-2)%n。也可以用快速幂直接求出。
二、若a与n不互素,可以用通用的方法求出。(此方法求出的应该不能再叫逆元了) 引入问题：求p=a/b%n。(b与n不互素) 已知：除以一个数b等价与乘以它的乘法逆元inv(b)。 但是此时b与n不互素,因此不能用扩展欧几里德和欧拉定理求解。 可以直接用公式：p=a%(b*n)/b;公式不难证明。此方法是在poj1845的讨论区看到的........
另外附上大神的文章：ACdreamer-逆元详解

热门文章