扩展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是质数，一定与
``