คำชี้แจงปัญหา
กำหนดจำนวนเต็ม 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 ลงตัว จะไม่มีตัวเลขใดตรงตามเงื่อนไขที่กำหนด
ตัวอย่าง
#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
