| ||||||||||
| 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 | |||||||||
谁能告诉我,我wa哪了?用拓展欧几里德敲的#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
void swap(int &a,int &b)
{
int t=a;
a=b;
b=t;
}
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int g=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*x;
return g;
}
int getxx(int t,int x,int b)
{
return fabs(x+t*b);
}
int getyy(int t,int y,int a)
{
return fabs(y-t*a);
}
int getaxby(int x,int y,int a,int b,int t)
{
return a*getxx(t,x,b)+b*getyy(t,y,a);
}
int getxy(int x,int y,int a,int b,int t)
{
return getxx(t,x,b)+getyy(t,y,a);
}
int main()
{
int a,b,c,x,y,xx,yy,t,g,t1,t2;
bool flag;
while(scanf("%d%d%d",&a,&b,&c)!=EOF&&a||b||c)
{
if(a==b)
{
c=c/a;
b=1;
a=1;
} //这句话去掉也是一样wa
flag=false;
if(a<b)
{
swap(a,b);
flag=true;
}
g=exgcd(a,b,x,y);
a=a/g;
b=b/g;
x*=c/g;
y*=c/g;
t1=y*g/(a*g);
// printf("x=%I64d y=%I64d t1=%I64d %I64d\n",x,y,t1,g);
if(t1*a/g-y>=0)t1--;
t2=t1+1;
// printf("t1,t2=%I64d,%I64d\n",t1,t2);
if(getxy(x,y,a,b,t1)>getxy(x,y,a,b,t2))
{
t=t2;
}
else if(getxy(x,y,a,b,t1)<getxy(x,y,a,b,t2))
{
t=t1;
}
else
{
if(getaxby(x,y,a,b,t1)>getxy(x,y,a,b,t2))
t=t2;
else
t=t1;
}
xx=getxx(t,x,b);
yy=getyy(t,y,a);
if(flag)
printf("%d %d\n",yy,xx);
else
printf("%d %d\n",xx,yy);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator