扩展gcd模板
ll exgcd(ll a, ll b, ll &x, ll &y){
ll d;
if(b == 0) {
x = 1;y = 0;
return a;
}
ll x1, y1;
d = exgcd(b, a%b, x1, y1);
x = y1;
y = x1-(a/b)*y1;
return d;
}
求的是ax+by=gcd(a,b)，对于ax+by=c。要先判断c是否能整除gcd(a,b)，否则无解。
例如求逆元。
ax≡1(mod)->ax +b*mod = 1
//求a的逆元
exgcd(a, mod, x, y);
while(x<0) x += mod;
printf("%lld\n", x%mod);//因为mod是质数，一定与
``
查看7道真题和解析
