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
|
package main
import "fmt"
func main() {
N := 55
D := 13
n := N
d := D
l := make([]int, 0)
for d != 0 {
t := n/d
l = append(l, t)
r := n%d
n,d=d,r
}
fmt.Printf("PGCD(%d, %d) = %d\n", N, D, n)
fmt.Println(l, len(l))
gcd := n
n,d = 1, l[len(l)-1]
for i := len(l) - 1 ; i >= 0 ; i-- {
t := n+d*l[i]
n,d = d,t
}
if len(l) & 1 == 1 {
n,d=-n,-d
}
fmt.Printf("%d*%d - %d*%d = %d = %d\n", N, n, D, d, gcd, n*N-d*D)
}
|
