題目敘述

請實作一程式可以要求使用者輸入3組資料，請輸出每一組資料內三個數字的最大公因數。

範例輸入

答題思路

多個數字的最大功因數（gcd，greatest common divisor）：

1

gcd(a, b, c) = gcd(a, gcd(b, c))

一、迴圈法

1
2
3
4
5
6
7
8
9


int gcd(int a,int b) {
    int r;
    while(b>0) {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

位元運算

1
2
3
4


int gcd(int a,int b) {
    while(b^=a^=b^=a%=b);
    return a;
}

另類迴圈法

1
2
3
4


int gcd(int a,int b) {
    if(b) while((a%=b) && (b%=a));
    return a+b;
}

二、遞迴法

輾轉相除法（歐幾里得算法）

1
2
3


int gcd(int x, int y) {
    return (y == 0)? x: gcd(y, x % y);
}

更相減損術

1
2
3


int gcd(int x, int y) {
    return (y == 0)? x: gcd1(x - y, y);
}

三、函式庫

Syntax for C++14

1
2
3
4
5
6


#include <algorithm>

int main() {
    cout << __gcd(a, b) << endl;
    return 0;
}

Syntax for C++17

1
2
3
4
5
6


#include <numeric>

int main() {
    cout << gcd(a, b) << endl;
    return 0;
}

參考答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


#include <iostream>

int gcd(int a, int b) {
    return (a == 0)? b: gcd(b % a, a);
}

int main() {
    int n = 3;
    
    while(n--) {
        int a, b, c;
        
        scanf("%d %d %d", &a, &b, &c);
        
        std::cout << gcd(gcd(a, b), c) << std::endl;
    }
    
    return 0;
}