Introduction to Programming (I)

Lab 6-4: 大數最大公因數 (15%)

Euclidean algorithm - Wikipedia

可以參考以下 pseudocode：

while b != 0
    t = b
    b = a % b
    a = t
return a

• 輸入：
  • 兩自然數字 \( a, b \) 並且各自不多於 36 位數字。
  • 兩自然數字的前後 18 位數字需分別輸入。
    • \( a = a_{first} \times 10^{18} + a_{second}, b = b_{first} \times 10^{18} + b_{second} \)
  • 需偵測不合法的輸入，並輸出 Invalid input 後提示使用者再次輸入該自然數。
  • 需支援重複輸入，使用者輸入 -1 則結束程式。
• 輸出：兩自然數字 \( a, b \) 的最大公因數 \( gcd(a, b) \)。
• 檔名：lab6_4_<學號>.cpp (e.g. lab6_4_106062802.cpp)

程式需提示使用者輸入兩數字 \( a, b \)，輸出兩數字 \( a, b \) 的最大公因數 \( gcd(a, b) \)。 使用者會在每次輸入時輸入任意整數，請考慮所有合法 long long 型態的數字輸入。

The number a, first part (input -1 to exit): <a_first>⏎
The number a, second part (input -1 to exit): <a_second>
The number a = <a>
The number b, first part (input -1 to exit): <b_first>⏎
The number b, second part (input -1 to exit): <b_second>⏎
The number b = <b>
The gcd(a, b) = <gcd(a, b)>

Example:

$ ./a.out
The number a, first part (input -1 to exit): 123492001107001353⏎
The number a, second part (input -1 to exit): 123492001107001353⏎
The number a = 123492001107001353123492001107001353
The number b, first part (input -1 to exit): 99396000891001089⏎
The number b, second part (input -1 to exit): 99396000891001089⏎
The number b = 99396000891001089099396000891001089
The gcd(a, b) = 3012000027000033003012000027000033

The number a, first part (input -1 to exit): 987654321⏎
The number a, second part (input -1 to exit): 200000000000000000⏎
The number a = 987654321200000000000000000
The number b, first part (input -1 to exit): 123456789⏎
The number b, second part (input -1 to exit): 200000000000000000⏎
The number b = 123456789200000000000000000
The gcd(a, b) = 400000000000000000

The number a, first part (input -1 to exit): 1234567890123456789⏎
Invalid input
The number a, first part (input -1 to exit): 123456789123456789⏎
The number a, second part (input -1 to exit): 1234567890123456789⏎
Invalid input
The number a, first part (input -1 to exit): 123456789123456789⏎
The number a, second part (input -1 to exit): 123456789123456789⏎
The number a = 123456789123456789123456789123456789
The number b, first part (input -1 to exit): 1111111110111111111⏎
Invalid input
The number b, first part (input -1 to exit): 111111111111111111⏎
The number b, second part (input -1 to exit): 1111111110111111111⏎
Invalid input
The number b, first part (input -1 to exit): 111111111111111111⏎
The number b, second part (input -1 to exit): 111111111111111111⏎
The number b = 111111111111111111111111111111111111
The gcd(a, b) = 9000000009000000009000000009

The number a, first part (input -1 to exit): -1⏎

$ ./a.out
The number a, first part (input -1 to exit): -2⏎
Invalid input
The number a, first part (input -1 to exit): 1⏎
The number a, second part (input -1 to exit): -2⏎
Invalid input
The number a, first part (input -1 to exit): 2⏎
The number a, second part (input -1 to exit): 2⏎
The number a = 2000000000000000002
The number b, first part (input -1 to exit): -1⏎

Reference:

• Big Number Calculator

Reference Code:

Credit: 林暐晉(110021134)

#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;

int main()
{
    unsigned long long long_a_a = 0, long_a_b = 0, long_b_a = 0, long_b_b = 0, t_a = 0, t_b = 0;
    while (1)
    {
        while (cout << "The number a, first part (input -1 to exit): ")
        {
            cin >> long_a_a;
            if (long_a_a == -1)
            {
                return 0;
            }
            if (long_a_a < 0 || long_a_a >= (long long)pow(10, 18))
            {
                cout << "Invalid input" << endl;
                continue;
            }
            cout << "The number a, second part (input -1 to exit): ";
            cin >> long_a_b;
            if (long_a_b == -1)
            {
                return 0;
            }
            if (long_a_b < 0 || long_a_b >= (long long)pow(10, 18))
            {
                cout << "Invalid input" << endl;
                continue;
            }
            if (long_a_a == 0 && long_a_b == 0)
            {
                cout << "Invalid input" << endl;
                continue;
            }
            if (long_a_a == 0)
            {
                cout << "The number a = " << long_a_b << endl;
            }
            else
            {
                cout << "The number a = " << long_a_a << setfill('0') << setw(18) << long_a_b << endl;
            }
            break;
        }
        while (cout << "The number b, first part (input -1 to exit): ")
        {
            cin >> long_b_a;
            if (long_b_a == -1)
            {
                return 0;
            }
            if (long_b_a < 0 || long_b_a >= (long long)pow(10, 18))
            {
                cout << "Invalid input" << endl;
                continue;
            }
            cout << "The number b, second part (input -1 to exit): ";
            cin >> long_b_b;
            if (long_b_b == -1)
            {
                return 0;
            }
            if (long_b_b < 0 || long_b_b >= (long long)pow(10, 18))
            {
                cout << "Invalid input" << endl;
                continue;
            }
            if (long_b_a == 0 && long_b_b == 0)
            {
                cout << "Invalid input" << endl;
                continue;
            }
            if (long_b_a == 0)
            {
                cout << "The number b = " << long_b_b << endl;
            }
            else
            {
                cout << "The number b = " << long_b_a << setfill('0') << setw(18) << long_b_b << endl;
            }
            break;
        }
        while (long_b_a != 0 || long_b_b != 0)
        {
            t_a = long_b_a;
            t_b = long_b_b;
            while (long_a_a >= long_b_a)
            {
                if (long_b_a == 0 && long_b_b != 0)
                {
                    long_a_b %= long_b_b;
                    long_a_a--;
                    if (long_a_a > (long long)pow(10, 18))
                    {
                        long_a_a++;
                        break;
                    }
                    long_a_b += (long long)pow(10, 18);
                }
                else
                {
                    long_a_a -= long_b_a;
                    if (long_a_b < long_b_b)
                    {
                        long_a_a--;
                        if (long_a_a > (long long)pow(10, 18))
                        {
                            long_a_a++;
                            long_a_a += long_b_a;
                            break;
                        }
                        long_a_b += (long long)pow(10, 18);
                        long_a_b -= long_b_b;
                    }
                    else
                    {
                        long_a_b -= long_b_b;
                    }
                }
            }
            long_b_a = long_a_a;
            long_b_b = long_a_b;
            long_a_a = t_a;
            long_a_b = t_b;
        }

        if (long_a_a == 0)
        {
            cout << "The gcd(a, b) = " << long_a_b << endl;
        }
        else
        {
            cout << "The gcd(a, b) = " << long_a_a << setfill('0') << setw(18) << long_a_b << endl;
        }

        cout << endl;
    }
    return 0;
}