Modular Multiplicative Inverse

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:

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).