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