乘法逆元模板

1. 扩展欧几里得

ll ex_gcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得（扩展gcd）
{
	if (a==0&&b==0) return -1;
	if (b==0){x=1;y=0;return a;}
	ll d=ex_gcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
 
ll mod_inverse(ll a,ll n)//乘法逆元，a与n必须互素
{
	ll x,y;
	ll d = ex_gcd(a,n,x,y);
	return (x%n+n)%n;
}

2. 费马小定理，快速幂

int find(int x)  //x与mod互素，且mod为素数
{  
    int k=mod-2,ans=1;  
    while(k)  
    {  
        if (k&1) ans=(ll)ans*x%mod;  
        x=(ll)x*x%mod;  
        k>>=1;  
    }  
    return ans;  
}  
//x在%mod下的逆元

/*已知p是质数且gcd(a, p) = 1，则 ap-1 ≡ 1 (mod p),  所以 a*ap-2 ≡ 1 (mod p)。
a^(p-2)就是a的逆元了*/