โปรแกรม C++ หาค่า X และ Y สุดท้ายเมื่อเปลี่ยนแปลงภายใต้เงื่อนไขที่กำหนด

พิจารณาว่าเรามีค่าเริ่มต้นของจำนวนเต็มบวกสองจำนวน X และ Y หาค่าสุดท้ายของ X และ Y ที่จะมีการเปลี่ยนแปลงบางอย่างดังนี้:

• step1 − ถ้า X = 0 และ Y = 0 ให้สิ้นสุดกระบวนการ มิฉะนั้นไปที่ step2
• step2 − ถ้า X >= 2Y ให้ตั้ง X = X - 2Y และไปที่ step1 มิฉะนั้นไปที่ step3
• step3 − ถ้า Y >= 2X ให้ตั้ง Y = Y - 2X และไปที่ step1 มิฉะนั้นสิ้นสุดกระบวนการ

ตัวเลข X และ Y จะอยู่ในช่วง [0 และ 10^18] ดังนั้นเราสามารถใช้แนวคิด Brute Force ได้

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

void alterNumber(long long x, long long y) {
    while (1) {
        if (x == 0 || y == 0)
            break;
        if (x >= 2 * y)
            x = x % (2 * y);
        else if (y >= 2 * x)
            y = y % (2 * x);
        else
            break;
    }
    cout << "X: " << x << "\n" << "Y: " << y;
}

int main() {
    long long x = 12, y = 5;
    alterNumber(x, y);
}

ผลลัพธ์

X: 0
Y: 1