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 <iostream> #include<cstdio> #include<cmath> using namespace std; int x,y; int gcd(int a,int b){ if(b==0){ x=1; y=0; return a; } else{ int result=gcd(b,a%b); int tem=x; x=y; y=tem-a/b*y; return result; } } int main() { //freopen("in.txt","r",stdin); int a,b,d; while(scanf("%d%d%d",&a,&b,&d)&&(a|b|d)){ int d1=gcd(a,b); if(d%d1!=0)printf("no solution\n"); else { a/=d1,b/=d1,d/=d1; gcd(a,b); x*=d;y*=d; bool f=0; int k1,k2,k; int ansx1,ansy1,ansx2,ansy2,ansx3,ansy3; //cout<<"x="<<x<<" "<<"y="<<y<<endl; //first k1=ceil(-x*1.0/b); k2=floor(y*1.0/a); if(b>a)k=min(k1,k2); else k=max(k1,k2); if(k>=k1&&k<=k2){ f=1; ansx1=x+k*b; ansy1=y-k*a; } //second k2=ceil(y*1.0/a); k=max(k1,k2); ansx2=x+k*b; ansy2=-(y-k*a); //third k1=floor(-x*1.0/b); k2=floor(y*1.0/a); k=min(k1,k2); ansx3=-(x+k*b); ansy3=y-k*a; int ansx,ansy; // cout<<ansx1<<" "<<ansy1<<endl; // cout<<ansx2<<" "<<ansy2<<endl; // cout<<ansx3<<" "<<ansy3<<endl; if(ansx2+ansy2<ansx3+ansy3){ ansx=ansx2; ansy=ansy2; } else if(ansx2+ansy2>ansx3+ansy3){ ansx=ansx3; ansy=ansy3; } else{ if(a*ansx2+b*ansy2<a*ansx3+b*ansy3){ ansx=ansx2; ansy=ansy2; } else { ansx=ansx3; ansy=ansy3; } } if(f){ if(ansx1+ansy1<ansx+ansy){ ansx=ansx1; ansy=ansy1; } else if(ansx1+ansy1==ansx+ansy){ if(a*ansx1+b*ansy1<a*ansx+b*ansy){ ansx=ansx1; ansy=ansy1; } } } printf("%d %d\n",ansx,ansy); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator