Trong hướng dẫn này, ta sẽ viết chương trình dựa trên khái niệm LCM. Như tiêu đề, ta phải tìm ba số nhỏ hơn hoặc bằng số cho trước sao cho LCM của chúng lớn nhất.
Hãy xem một ví dụ.
Trước khi đi vào bài toán, hãy xem LCM là gì và viết chương trình tìm LCM.
LCM là bội chung nhỏ nhất của các số. Còn gọi là ước chung nhỏ nhất. Với hai số dương a và b, LCM là số nguyên nhỏ nhất chia hết cho cả a và b.
Nếu các số cho trước không có ước chung, LCM là tích của các số đó.
Ví dụ
Viết chương trình tìm LCM của hai số dương cho trước.
#include <iostream> using namespace std; int main() { int a = 4, b = 5; int maximum = max(a, b); while (true) { if (maximum % a == 0 && maximum % b == 0) { cout << "LCM: " << maximum << endl; break; } maximum++; } }
Đầu ra
Nếu chạy chương trình trên, bạn sẽ nhận được đầu ra sau:
20
Ta đã xem LCM là gì và chương trình tìm LCM của hai số dương.
Hãy xem các bước giải bài toán chính.
- Nếu số là lẻ, ba số có LCM lớn nhất là n, n - 1, và n - 2.
- Nếu số là chẵn và GCD của n và n - 3 là 1, ba số là n, n - 1, và n - 3.
- Ngược lại, ba số là n - 1, n - 2, và n - 3.
Ví dụ
Xem mã dưới đây:
#include <bits/stdc++.h> using namespace std; void threeNumbersWithMaxLCM(int n) { if (n % 2 != 0) { cout << n << " " << (n - 1) << " " << (n - 2); } else if (__gcd(n, (n - 3)) == 1) { cout << n << " " << (n - 1) << " " << (n - 3); } else { cout << (n - 1) << " " << (n - 2) << " " << (n - 3); } cout << endl; } int main() { int n = 18; threeNumbersWithMaxLCM(n); return 0; }
Đầu ra
Nếu thực thi chương trình trên, bạn sẽ nhận được kết quả sau:
17 16 15
Kết luận
Nếu bạn có thắc mắc, hãy đề cập trong phần bình luận.