ACM数论----逆元及其求法

2019-04-14 17:29发布

一.逆元是什么?为什么引入逆元 (1)逆元,又称为数论倒数。这里和普通的倒数是不一样的,普通倒数可能为小数,而数论倒数一定是个整数。 数论概念:对于正整数 aa 和 pp,如果有 ax≡1(modp),那么把这个同余方程中 x 的最小正整数解叫做 a模 p的逆元。 即 ax % p = 1中 x 的最小正整数解就是a关于模数p的逆元。 (2)为什么引入逆元?(只适用于除法取模运算) 这里引入取模的概念: a +  b) % p = (a%p +  b%p) %p  (对) (a  -  b) % p = (a%p  -  b%p) %p  (对) (a  *  b) % p = (a%p *  b%p) %p  (对) (a  /  b) % p = (a%p  /  b%p) %p  (错) 我们都知道取模运算对于除法是不成立的,那么如果模运算中出现了除法是不是就无法计算了呢?伟大的数学家于是给出了逆元这个东西。 ax % p = 1,这里x不一定等于 1 / a , 因为加入了取模。比如 3 * 2%5 = 1 , 这里的2不就相当于 1 / 3的作用吗?于是我们就说 2 是3关于模数5的逆元。这就是逆元产生的意义。于是,我们在计算除法取模时,可以把除数变为他的逆元,把除法取模运算变为乘法取模运算,在二式等价背景下,变除为乘,间接实现取模运算,这就是逆元的魅力!(我们下面用inv(a)代表a的逆元)   由上可知: (a/b)%p  = (a * inv(b))%p = (a%p * inv(b)%p)%p    (即除以一个数取模等于乘以这个数的逆元取模)   二、如何求逆元 (1)费马小定理(要求:模数p为素数,且a 与 p互质即gcd(a,p) == 1) 由费马小定理知: a^(p-1) ≡ 1(mod p)即 a^(p-1)%p = 1 已知:a*inv(a)%p = 1 所以:a*inv(a)%p = a^(p-1)%p 则:inv(a)%p = a^(p-2)%p 于是这里用到快速幂 + 费马小定理来求逆元。 代码:  LL power(LL a,LL b)//快速幂 { a%=p; LL ans = 1; while(b){ if(b&1)ans = (ans*a)%p; b>>=1; a = (a*a)%p; } return ans; } int main() { while(scanf("%lld%lld",&n,&p)!=EOF&&n){ printf("%lld ",power(n,p-2));//求n关于p的逆元 } return 0; } 时间复杂度 O(log(p)) (2)拓展欧几里得算法求逆元(不要求模数p为素数,要求a, p互质即gcd(a,p)==1 )   我们知道 拓展欧几里得 求解 : ax + py = 1(a与p互质即gcd(a,p) = 1) 则: ax%p + py%p = 1%p 即:ax % p = 1%p 即: ax ≡ 1(mod p) 所以x的最小整数解就是a关于p的逆元,所以我们只要求解 ax + py = 1的最小正整数解 x 即可 代码: LL ex_gcd(LL a,LL b,LL &x,LL &y){ if(b==0){x = 1;y = 0;return a;} int ans = ex_gcd(b,a%b,x,y); int temp = x; x = y; y = temp - (a/b)*y; return ans; } LL inv(LL a,LL b){ LL x,y; int ans = ex_gcd(a,b,x,y); if(x<0)x = (x%b + b)%b;//有可能<0,我们让他>0 if(ans==1)return x;//ab互斥有解 else return -1;//否则返回-1 } int main() { while(scanf("%lld%lld",&n,&p)!=EOF&&n){ printf("%lld ",inv(n,p)); } return 0; } 时间复杂度 O(log(p))