【拓展欧几里得】【快速幂】【线性递推】P3811 【模板】乘法逆元

原题地址 参 考
拓展欧几里得(单个查找，p可以为合数)
void Exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) x = 1, y = 0;
else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
ll x, y;
Exgcd (a, p, x, y);
x = (x % p + p) % p;
printf ("%d/n", x); //x是a在mod p下的逆元
}

快速幂(单个查找，p必须为质数)
ll quick_pow(ll a,ll b,ll mod){//a^b%mod
ll ans=1,base=a;
while(b){
if(b&1) ans*=base,ans%=mod;
base*=ba

【拓展欧几里得】【快速幂】【线性递推】P3811 【模板】乘法逆元最先出现在Python成神之路。