| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
=。=秒过#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
LL ret;
if(a==0)
{
x=0;y=1;
return b;
}
else
{
LL tx,ty;
ret=exgcd(b%a,a,tx,ty);
x=ty-b/a*tx;
y=tx;
return ret;
}
}
int main()
{
LL a,b,c,A,B,K,d,x,y,ax,ay,X,Y;
while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF)
{
if(a==0&&b==0&&c==0)return 0;
LL ans=0x7FFFFFFFFFFFFFFF;
/* Ax+By=K */
A=a;B=b;K=c;
d=exgcd(A,B,x,y);
if(K%d==0)
{
X=(x*(K/d)%(B/d)+B/d)%(B/d);
Y=(K-A*X)/B;
if(ans>(X+Y)&&X>=0&&Y>=0)
{
ans=X+Y;
ax=X;
ay=Y;
}
Y=(y*(K/d)%(A/d)+A/d)%(A/d);
X=(K-B*Y)/A;
if(ans>(X+Y)&&X>=0&&Y>=0)
{
ans=X+Y;
ax=X;
ay=Y;
}
}
/* Ax=K+By > Ax-By=K*/
A=a;B=b;K=c;
d=exgcd(A,B,x,y);
if(K%d==0)
{
X=(x*(K/d)%(B/d)+B/d)%(B/d);
Y=(A*X-K)/B;
if(ans>(X+Y)&&X>=0&&Y>=0)
{
ans=X+Y;
ax=X;
ay=Y;
}
Y=(y*(K/d)%(A/d)+A/d)%(A/d);
X=(K-B*Y)/A;
if(ans>(X+Y)&&X>=0&&Y>=0)
{
ans=X+Y;
ax=X;
ay=Y;
}
}
/* By-Ax=K */
A=a;B=b;K=c;
d=exgcd(A,B,x,y);
if(K%d==0)
{
X=(x*(K/d)%(B/d)+B/d)%(B/d);
Y=(K+A*X)/B;
if(ans>(X+Y)&&X>=0&&Y>=0)
{
ans=X+Y;
ax=X;
ay=Y;
}
Y=(y*(K/d)%(A/d)+A/d)%(A/d);
X=(B*Y-K)/A;
if(ans>(X+Y)&&X>=0&&Y>=0)
{
ans=X+Y;
ax=X;
ay=Y;
}
}
if(ans==0x7FFFFFFFFFFFFFF)printf("no solution\n");
else printf("%I64d %I64d\n",ax,ay);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator