คำชี้แจงปัญหา
ค่าที่กำหนดของ A และ B ให้หาค่าจำนวนเต็มบวกขั้นต่ำของ X ที่สามารถทำได้ในสมการ X =P*A + Q*B โดยที่ P และ Q สามารถเป็นศูนย์หรือจำนวนเต็มบวกหรือค่าลบใดๆ
ตัวอย่าง
ถ้า A =2 และ B =4 คำตอบจะเป็น 2
อัลกอริทึม
- เราต้องหา P และ Q ให้ P*A> P*B และ P*A – P*B เป็นจำนวนเต็มบวกขั้นต่ำ
- ปัญหานี้แก้ไขได้ง่ายๆ ด้วยการคำนวณ GCD ของตัวเลขทั้งสอง)
ตัวอย่าง
#include <iostream>
using namespace std;
int getGcd(int a, int b) {
if (a == 0) {
return b;
}
return getGcd(b % a, a);
}
int main() {
cout << "Answer = " << getGcd(2, 4) << endl;
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Answer = 2
