| ||||||||||
| 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