Uvalive 6428 A+B(拡張ユークリッドアルゴリズム)
1688 ワード
【タイトルリンク】:click here~~
【題目大意】:a*x+b*y=cのような方程式を満たすことを求め、整数解があるかどうかを問う(a,b,c<10^18)
【考え方】ユークリッドアルゴリズムを拡張し、特判がゼロに等しい場合に注意する
コード:
【題目大意】:a*x+b*y=cのような方程式を満たすことを求め、整数解があるかどうかを問う(a,b,c<10^18)
【考え方】ユークリッドアルゴリズムを拡張し、特判がゼロに等しい場合に注意する
コード:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b,c;
LL gcd(LL a,LL b)
{
return b==0?a:gcd(b,a%b);
}
// a * n + b * m = gcd(n, m)
// (x0, y0)
// : (x0 + k * b / g, y0 - k * a / g)
LL ext_gcd(LL &a,LL &b,LL n,LL m) // Extended Euclidean Algorithm
{
if(m==0)
{
a=1;
b=0;
return n;
}
LL d=ext_gcd(b,a,m,n%m);
b-=n/m*a;
return d;
}
int main()
{
while(scanf("%lld %lld %lld",&a,&b,&c)!=EOF)
{
if(!a&&!b) // special judge the a and b if it value 0
{
if(!c) puts("YES");
else puts("NO");
continue;
}
if(!a)
{
if((c%b)==0) puts("YES");
else puts("NO");
continue;
}
if(!b)
{
if((c%a)==0) puts("YES");
else puts("NO");
continue;
}
LL x,y,g;
g=ext_gcd(x,y,a,b);
if((c%g)!=0)
{
puts("NO");
continue;
}
LL x0=b/g;
LL y0=a/g;
x=((c/g%x0)*(x%x0)%x0+x0)%x0;
y=(c-x*a)/b;
bool ok=false;
while(y>0)
{
if(gcd(x,y)==1)
{
ok=true;
break;
}
x+=x0;y-=y0;
}
if(ok) puts("YES");
else puts("NO");
}
return 0;
}