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