乘法逆元

定义

对于一个数a和模m，存在一个数x，使得：

$$a\ast x\equiv 1(modm)$$

则x是a在模m下的逆元。只有当a和m是互质时（即 gcd⁡(a,m)=1），才存在这样的逆元x。

实现

快速幂算法

费马小定理：如果p是一个质数，而整数a不是p的倍数，则有a^(p-1)≡1(mod p)。
推论：a^(-1)≡a^(p-2)(mod p)

int fast_pow(int a,int b);
int mod_inverse(const int a,const int p) 
{
	return fast_pow(a,p-2);
}

扩展欧几里得算法

void extended_gcd(const int& a, const int& b, int& x, int& y) {  
    if (b == 0)  
    {  
        x = 1, y = 0;  
        return;  
    }  
    extended_gcd(b, a % b, y, x);  
    y -= a / b * x;  
}