Codeforces 7C 扩展欧几里得

扩展欧几里得是计算 ax + by = gcd(a,b) 的 x,y的整数解。

现在是ax + by + c = 0;

只要 -c 是 gcd(a,b) 的整数倍时有整数解，整数解是 x = x*(-c)/gcd(a,b) ; y = y*(-c)/gcd(a,b);

#include <bits/stdc++.h>using namespace std;typedef long long ll;void gcd(ll a,ll b,ll& d,ll& x,ll& y) {
    if(!b) {d=a;x=;y=;}
    else {
        gcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}int main()
{
    ll a,b,c;
    ll d,x,y;
    scanf("%lld%lld%lld",&a,&b,&c);
    gcd(a,b,d,x,y);
    if(c%d==) {
        x = -x*c/d;
        y = -y*c/d;
        printf("%lld %lld\n",x,y);
    }
    else printf("-1\n");    return ;
}