1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <stdio.h>
struct Solution { int gcd, x, y; };
int s[10000], t[10000], r[10000], q[10000];
int i;
void INIT_EEC_Table(int A, int B){
s[1] = t[0] = q[0] = 0;
s[0] = t[1] = 1;
r[0] = A, r[1] = B;
q[1] = A/B;
}
void Show_Table(){
printf("I\t\tS\t\tT\t\tR\t\tQ\n");
for(int j = 0; j<=i; j++)
printf("%d : \t%d\t\t%d\t\t%d\t\t%d\n",j,s[j],t[j],r[j],q[j]);
}
void EEC(int A,int B){
INIT_EEC_Table(A,B);
i = 1;
while(r[i-1]%r[i]){
r[i+1] = (r[i-1] - r[i] * q[i]);
s[i+1] = (s[i-1] - s[i]*q[i]);
t[i+1] = (t[i-1] - t[i]*q[i]);
++i;
q[i] = (r[i-1]/r[i]);
}
Show_Table();
}
Solution extendedEuclid(int a, int b) {
int q = a / b, r = a % b;
if (r == 0) return Solution{ b, 0, 1 };
Solution s = extendedEuclid(b, r);
return Solution{ s.gcd, s.y, s.x - q * s.y };
}
int main(int argc, char** argv){
int A, B;
scanf("%d %d",&A,&B);
EEC(A,B);
printf("%d %d\n",s[i],t[i]);
Solution s = extendedEuclid(A,B);
printf("%d %d\n",s.x, s.y);
return 0;
}
|
