#include <bits/stdc++.h>
using namespace std;
long long int A, B, c, r[100001], a[100001], b[100001], q[100001];
long long int gcd(long long int x, long long int y)
{
if(x%y==0)
return y;
return gcd(y, x%y);
}
int main()
{
printf("Ax+By=C 형태로 정리한 부정방정식의 A, B, C값을 차례로 입력하십시오.");
scanf("%lld %lld %lld", &A, &B, &c);
long long int w, e, m;
w=abs(A);
e=abs(B);
if(A==0&&B!=0)
{
if(c%B==0)
{
printf("x=1, y=%lld", c/B);
return 0;
}
printf("정수해가 존재하지 않습니다.");
return 0;
}
else if(A!=0&&B==0)
{
if(c%A==0)
{
printf("x=%lld, y=1", c/A);
return 0;
}
printf("정수해가 존재하지 않습니다.");
return 0;
}
else if(A==0&&B==0)
{
if(c==0)
{
printf("x=1, y=1");
return 0;
}
printf("정수해가 존재하지 않습니다.");
return 0;
}
if(w<e)
{
m=w;
w=e;
e=m;
}
long long int t;
t=gcd(w, e);
if(c%t!=0)
{
printf("정수해가 존재하지 않습니다.");
return 0;
}
long long int p=c/t;
if(A>B&&B>0)
{
long long int k;
r[0]=A;
r[1]=B;
for(int i=2;; i++)
{
r[i]=r[i-2]%r[i-1];
if(r[i]==0)
{
k=i-1;
break;
}
}
for(int i=1; i<=k; i++)
{
q[i]=r[i-1]/r[i];
}
a[k]=-q[k-1];
b[k]=1;
for(int i=k-1; i>=1; i--)
{
a[i]=-(a[i+1]*q[i-1])+b[i+1];
b[i]=a[i+1];
}
printf("x=%lld+%lldk, y=%lld-%lldk", a[1]*p, B/t, b[1]*p, A/t);
}
else if(A>B&&B<0&&A>0)
{
int k;
r[0]=A;
r[1]=-B;
for(int i=2;; i++)
{
r[i]=r[i-2]%r[i-1];
if(r[i]==0)
{
k=i-1;
break;
}
}
for(int i=1; i<=k; i++)
{
q[i]=r[i-1]/r[i];
}
a[k]=-q[k-1];
b[k]=1;
for(int i=k-1; i>=1; i--)
{
a[i]=-(a[i+1]*q[i-1])+b[i+1];
b[i]=a[i+1];
}
printf("x=%lld+%lldk, y=%lld-%lldk", a[1]*p, B/t,-b[1]*p, A/t);
}
else if(A>B&&A<0)
{
int k;
r[0]=-A;
r[1]=-B;
for(int i=2;; i++)
{
r[i]=r[i-2]%r[i-1];
if(r[i]==0)
{
k=i-1;
break;
}
}
for(int i=1; i<=k; i++)
{
q[i]=r[i-1]/r[i];
}
a[k]=-q[k-1];
b[k]=1;
for(int i=k-1; i>=1; i--)
{
a[i]=-(a[i+1]*q[i-1])+b[i+1];
b[i]=a[i+1];
}
printf("x=%lld+%lldk, y=%lld-%lldk", -a[1]*p, B/t, -b[1]*p, A/t);
}
else if(A<B&&A>0)
{
int k;
r[0]=B;
r[1]=A;
for(int i=2;; i++)
{
r[i]=r[i-2]%r[i-1];
if(r[i]==0)
{
k=i-1;
break;
}
}
for(int i=1; i<=k; i++)
{
q[i]=r[i-1]/r[i];
}
a[k]=-q[k-1];
b[k]=1;
for(int i=k-1; i>=1; i--)
{
a[i]=-(a[i+1]*q[i-1])+b[i+1];
b[i]=a[i+1];
}
printf("x=%lld+%lldk, y=%lld-%lldk", b[1]*p, B/t, a[1]*p, A/t);
}
else if(A<B&&A<0&&B>0)
{
int k;
r[0]=B;
r[1]=-A;
for(int i=2;; i++)
{
r[i]=r[i-2]%r[i-1];
if(r[i]==0)
{
k=i-1;
break;
}
}
for(int i=1; i<=k; i++)
{
q[i]=r[i-1]/r[i];
}
a[k]=-q[k-1];
b[k]=1;
for(int i=k-1; i>=1; i--)
{
a[i]=-(a[i+1]*q[i-1])+b[i+1];
b[i]=a[i+1];
}
printf("x=%lld+%lldk, y=%lld-%lldk", -b[1]*p, B/t, a[1]*p, A/t);
}
else if(A<B&&B<0)
{
int k;
r[0]=-B;
r[1]=-A;
for(int i=2;;i++)
{
r[i]=r[i-2]%r[i-1];
if(r[i]==0)
{
k=i-1;
break;
}
}
for(int i=1;i<=k;i++)
{
q[i]=r[i-1]/r[i];
}
a[k]=-q[k-1];
b[k]=1;
for(int i=k-1;i>=1;i--)
{
a[i]=-(a[i+1]*q[i-1])+b[i+1];
b[i]=a[i+1];
}
printf("x=%lld+%lldk, y=%lld-%lldk", -b[1]*p, B/t, -a[1]*p, A/t);
}
}