1 __int64 a,b,x,y;
 2 __int64 extend_euclid(__int64 a,__int64 b,__int64 &x,__int64 &y)
 3 {
 4     if (b==0)
 5     {
 6         x=1;
 7         y=0;
 8         return a;
 9     }
10     int d=extend_euclid(b,a%b,x,y);
11     int t=x;
12     x=y;
13     y=t-a/b*y;
14     return d;
15 }