[数论]EX_GCD

模板

//拓展欧几里德求解ax+by=gcd(a,b)的一组解
ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
    if (b==0)
    {
        x=1,y=0;
        return a;
    }
    else
    {
        ll r=ex_gcd(b,a%b,y,x);
        y-=x*(a/b);
        return r;
    }
}
//返回的bool值表示该方程是否有解
bool linear_equation(int a,int b,int c,int &x,int &y)
{
    int d=ex_gcd(a,b,x,y);
    if (c%d) return false;
    int k=c/d;
    x*=k;y*=k;
    return true;
}