Problem Solving►UVa

UVa 10104 - Euclid Problem

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

參考：
http://www.csie.ntnu.edu.tw/~u91029/Divisor.html#5
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

基本上就是擴展歐幾里得的練習題，不過理解上總覺得有點轉不過來。
老實說還有很多模糊的地方就是了，我的數學R…

每階段都可以分成三部份去看：

  1. 輾轉相除求出餘數
  2. 餘數的相等形式
  3. 欲求出的等式

以 a = 47, b = 30 來看:(連續三行順序如上所述，除了 init 那)
而因為是遞迴去實作，順序可從下面往上看，可能比較好理解。

1 = 0 x 0 + 1
1 = 1 x 1 + 0 x 0
init: (i, j) = (1, 0)

4 = 1 x 4 + 0
0 = 4 x 1 + 1 x -4
1 = 4 x 0 + 1 x 1

13 = 4 x 3 + 1
1 = 13 x 1 + 4 x -3
1 = 13 x 1 + 4 x -3

17 = 13 x 1 + 4
4 = 17 x 1 + 13 x -1
1 = 17 x -3 + 13 x 4

30 = 17 x 1 + 13
13 = 30 x 1 + 17 x -1
1 = 30 x 4 + 17 x -7

47 = 30 x 1 + 17
17 = 47 x 1 + 30 x -1
1 = 47 x -7 + 30 x 11

每次將上一次 3. 等式 中的值用現在所算出的餘數形式去做替換。

1
2
3
int t = i;
i = j;
j = t - (a / b) * j;

就是在做這件事。

舉例來說，用 17 = 47 x 1 + 30 x -1，把 1 = 30 x 4 + 17 x -7 中的 17 換掉，
就變成了 1 = 30 x 4 + (47 x 1 + 30 x -1) x -7 = 47 x -7 + 30 x 11。

EXGCD
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
#include <cstdio>

void gcdEX(int a, int b, int &i, int &j, int &d)
{
    // 問題已分割至最小，i j 很好算。
    if (b == 0)
    {
        printf("%d = 0 x 0 + %d\n", a, a);
        printf("%d = %d x 1 + 0 x 0\n", a, a);
        d = a; // 最大公因數為 a
        i = 1;
        j = 0; // 此時的 i j
        printf("init: (i, j) = (%d, %d)\n\n", i, j);
        return;
    }

    // Divide + Conquer：輾轉相除。
    gcdEX(b, a % b, i, j, d);

    printf("%d = %d x %d + %d\n", a, b, a / b, a % b);
    printf("%d = %d x 1 + %d x %d\n", a % b, a, b, -a/b);//(a % b - a) / b => -(a/b)
    // Combine：利用小問題的結果，計算出現在這個問題的 i j。
    int t = i;
    i = j;
    j = t - (a / b) * j;

    printf("%d = %d x %d + %d x %d\n\n", d, a, i, b, j);
}
int main()
{

    int i, j, d;
    gcdEX(47, 30, i, j, d);
    return 0;
}

至於非遞迴的版本，就…。

Code

UVa 10104
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
#include <cstdio>

void gcdEX(int a, int b, int &i, int &j, int &d)
{
    if (b == 0)
    {
        d = a; // 最大公因數為 a
        i = 1;
        j = 0; // 此時的 i j
        return;
    }

    gcdEX(b, a % b, i, j, d);

    int t = i;
    i = j;
    j = t - (a / b) * j;
}
inline int get_num()
{
    int n = 0;
    char c;
    while ((c = getchar()) != '\n' && c != ' ' && c != EOF)
        n = n * 10 + c - '0';
    if (c == EOF)
        return -1;
    return n;
}
int main()
{
    int a, b;
    while ((a = get_num()) != -1)
    {
        b = get_num();
        int i, j, d;
        gcdEX(a, b, i, j, d);
        printf("%d %d %d\n", i, j, d);
    }

    return 0;
}