ข้อความโจทย์
กำหนดค่า 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
