Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4147 Accepted Submission(s): 1727
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 int a,b,x,y,d; 7 int gcd(int a, int b) 8 { 9 if(b == 0) 10 { 11 x = 1; 12 y = 0; 13 return a; 14 } 15 d = gcd(b, a % b); 16 int temp = x; 17 x = y; 18 y = temp - a / b * y; 19 return d; 20 } 21 int main() 22 { 23 while(scanf("%d%d", &a, &b) != EOF) 24 { 25 d = gcd(a, b); 26 if(1 % d) // 如果c % gcd == 1就无解 27 { 28 printf("sorry\n"); 29 continue; 30 } 31 x = x / d; // 特解 32 y = y / d; 33 if(x > 0) // x 大于0直接输出 34 printf("%d %d\n",x, y); 35 else 36 { 37 int t = (-1) * x / b * d; 38 //cout<<x<<" "<<b<<" "<<d<<endl; 39 int k = x + b / d * t; //当前的t下的x值 40 if(k < 0) 41 { 42 t++; //当前的t所求的x为负,取下一个点 43 44 } 45 printf("%d %d\n", x + b / d * t, y - a / d * t); 46 47 } 48 } 49 return 0; 50 }
原文:http://www.cnblogs.com/zhaopAC/p/5206891.html