【Codeforces】7C. Line【exgcd】

C. Line

【题目描述】

传送门

【题解】
根据ax+by=gcd(a,b)一定有解。

我们就可以将式子变成ax+by=-c/gcd(a,b)*gcd(a,b)

移项得ax/(-c/gcd(a,b))+by/(-c/gcd(a,b))=gcd(a,b)

用exgcd求出x/(-c/gcd(a,b))y/(-c/gcd(a,b))

然后乘回去就可以了

代码如下

#include<cstdio>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y){if(b==0){x=1,y=0;return a;}LL t=exgcd(b,a%b,y,x);y-=a/b*x;return t;}
int main(){
    LL A,B,C,x,y;scanf("%lld%lld%lld",&A,&B,&C);
    LL T=exgcd(A,B,x,y);
    if(C%T==0) printf("%lld %lld\n",-x*C/T,-y*C/T);
    else printf("-1\n");
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部