Đề bài
Cho hai số nguyên p và q, nhiệm vụ là tìm số x nhỏ nhất có thể sao cho q % x = 0 và x % p = 0. Nếu điều kiện không đúng cho bất kỳ số nào, in -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, rõ ràng q sẽ chia hết 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ủ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
Ví dụ mã nguồn
#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 biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:
Kết quả
Minimum value = 3