โปรแกรม C++ หาค่าต่ำสุดที่หารตัวหนึ่งลงตัวและหารด้วยอีกตัวลงตัว

ข้อความโจทย์

กำหนดจำนวนเต็มสองจำนวน p และ q งานคือการหาจำนวน x ที่น้อยที่สุดที่ทำให้ q % x = 0 และ x % p = 0 หากเงื่อนไขไม่เป็นจริงสำหรับตัวเลขใดๆ ให้พิมพ์ -1

ตัวอย่าง

If p = 3 and q = 66 then answer is 3 as:
66 % 3 = 0
3 % 3 = 0

อัลกอริทึม

• หากตัวเลข x ตอบสนองเงื่อนไขที่กำหนด จะชัดเจนว่า q จะหาร p ลงตัว คือ q % p = 0 เพราะ x เป็นพหุคูณของ p และ q เป็นพหุคูณของ x
• ดังนั้นค่าต่ำสุดที่เป็นไปได้ของ x จะเป็น GCD ของ p และ q และเมื่อ q ไม่หาร p ลงตัว ตัวเลขใดๆ ก็จะไม่ตอบสนองเงื่อนไขที่กำหนด

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

#include <bits/stdc++.h>
using namespace std;

int getMinValue(int p, int q) {
    if (q % p == 0) {
        return __gcd(p, q);
    }
    return -1;
}

int main() {
    int p = 3;
    int q = 66;
    cout << "Minimum value = " << getMinValue(p, q) << endl;
    return 0;
}

ผลลัพธ์

Minimum value = 3