Objective: To calculate modular multiplicative inverse of a number.(Refer to the link if you dont know what this term means)
Solution:
Two possible solutions are very nicely explained in the Wikipedia link. So, i will just share C++ implementations using both the methods
Using Extended Euclid:
Use modular exponentiation from here
Modular inverse is same as mod_exp(a,MOD-2,MOD).
Solution:
Two possible solutions are very nicely explained in the Wikipedia link. So, i will just share C++ implementations using both the methods
Using Extended Euclid:
void extended_gcd(int a, int b, int &gcd, int &x, int &y) { x=0; y=1; gcd=b; int u=1,v=0,m,n,q,r; while(a!=0) { q=gcd/a; r=gcd%a; m=x-u*q; n=y-v*q; gcd=a; a=r; x=u; y=v; u=m; v=n; } } LL mod_inv(int a) { int gcd,x,y; extended_gcd(a,MOD,gcd,x,y); if(gcd==1) return (LL)((x+MOD)%MOD); }Using Euler's Theorem:
Use modular exponentiation from here
Modular inverse is same as mod_exp(a,MOD-2,MOD).
No comments:
Post a Comment