Tuyên bố vấn đề
Cho hai số nguyên p và q, nhiệm vụ là tìm số x nhỏ nhất có thể có sao cho q% x =0 và x% p =0. Nếu các điều kiện không đúng với bất kỳ số nào, thì in ra -1.
Ví dụ
If p = 3 and q = 66 then answer is 3 as: 66 % 3 = 0 3 % 3 = 0
Thuật toán
- Nếu một số x thỏa mãn điều kiện đã cho, thì rõ ràng q sẽ chia cho p tức là q% p =0 vì x là bội của p và q là bội của x
- Vì vậy, giá trị nhỏ nhất có thể có của x sẽ là GCD của p và q và khi q không chia hết cho p thì không có số nào thỏa mãn điều kiện đã cho
Ví dụ
#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;
} Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Đầu ra
Minimum value = 3