Romantic（裸扩展欧几里德）

Romantic

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3944 Accepted Submission(s): 1638

Problem Description

The Sky is Sprite.
The Birds is Fly in the Sky.
The Wind is Wonderful.
Blew Throw the Trees
Trees are Shaking, Leaves are Falling.
Lovers Walk passing, and so are You.
................................Write in English class by yifenfei

Girls are clever and bright. In HDU every girl like math. Every girl like to solve math problem!
Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to satisfy X*a + Y*b = 1. If no such answer print "sorry" instead.

Input

The input contains multiple test cases.
Each case two nonnegative integer a,b (0<a, b<=2^31)

Output

output nonnegative integer X and integer Y, if there are more answers than the X smaller one will be choosed. If no answer put "sorry" instead.

Sample Input

51
44
79

Sample Output

2 -3
sorry
7 -3

题解：

等式已经说了，因为x无符号；所以x就只能是正数；下面是无符号的定义：

/*****************************************************/

计算机里的数是用二进制表示的，最左边的这一位一般用来表示这个
数是正数还是负数，这样的话这个数就是有符号整数。如果最左边这
一位不用来表示正负，而是和后面的连在一起表示整数，那么就不能
区分这个数是正还是负，就只能是正数，这就是无符号整数。

/****************************************************/

找到x，就得到y了；

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<vector>
 7 #define mem(x,y) memset(x,y,sizeof(x))
 8 using namespace std;
 9 typedef long long LL;
10 const int INF=0x3f3f3f3f;
11 /*
12 计算机里的数是用二进制表示的，最左边的这一位一般用来表示这个
13 数是正数还是负数，这样的话这个数就是有符号整数。如果最左边这
14 一位不用来表示正负，而是和后面的连在一起表示整数，那么就不能
15 区分这个数是正还是负，就只能是正数，这就是无符号整数。
16 */
17 void e_gcd(LL a,LL b,LL &d,LL &x,LL &y){
18     if(!b){
19         d=a;
20         x=1;
21         y=0;
22     }
23     else{
24         e_gcd(b,a%b,d,x,y);//写成a&b了。。。错了半天 
25         LL temp=x;
26         x=y;
27         y=temp-a/b*y;
28     }
29 }
30 void cal(LL a,LL b,LL c){
31     LL x,y,d;
32     e_gcd(a,b,d,x,y);
33 //    printf("%lld %lld %lld 
",d,x,y);
34     if(c%d!=0){
35         puts("sorry");
36         return;
37     }
38     x*=c/d;//c,d都是1，可以省略；
39     //x=x0+b/d*t;
40     b/=d;//这个要记清。。。。。 
41     if(b<0)b=-b;
42     LL ans=x%b;
43     if(ans<=0)ans+=b;//写成<=b了，又错半天。。。 
44     printf("%lld %lld
",ans,(1-ans*a)/b); 
45 }
46 int main(){
47     LL a,b;
48     while(~scanf("%lld%lld",&a,&b)){
49         cal(a,b,1);
50     }
51     return 0;
52 }