Hướng dẫn giải của Bội số (đề HSG 9 Phú Thọ 2014-2015)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Tìm bội chung nhỏ nhất (BSCNN) của hai số tự nhiên a, b với a, b ≤ 10^10. Đọc từ BSCNN.INP, ghi ra BSCNN.OUT. Kết quả có thể lên tới ~10^20, vượt quá long long nên cần kiểu __int128 để tính và in.
Sub 1: Vét cạn trên bội của số lớn — ~O(min(a, b))~
Lấy số lớn M = max(a, b), thử các bội M, 2M, 3M, ... cho tới khi chia hết cho số nhỏ m = min(a, b). Bội đầu tiên như vậy chính là BSCNN. Cách này đúng nhưng số bước có thể lên đến 10^10.
Kết quả chấm: đạt 32/32 test (SUB ok 32/32, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
typedef __int128 lint; // BSCNN có thể lên tới 10^20, vượt long long
void inSo(lint x) {
if (x == 0) { cout << 0; return; }
string s;
while (x > 0) { s += char('0' + (int)(x % 10)); x /= 10; }
reverse(s.begin(), s.end());
cout << s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BSCNN.INP", "r")) {
freopen("BSCNN.INP", "r", stdin);
freopen("BSCNN.OUT", "w", stdout);
}
long long a, b;
cin >> a >> b;
long long lo = min(a, b), hi = max(a, b);
// Vét cạn: thử các bội của số lớn hi, lấy bội đầu tiên chia hết cho số nhỏ lo
lint x = hi;
while (x % lo != 0) x += hi;
inSo(x);
cout << "\n";
return 0;
}
Sub 2: Công thức qua UCLN — ~O(log(max))~
BSCNN(a, b) = a·b / UCLN(a, b). Chia a cho UCLN trước rồi mới nhân với b để tránh tràn số. Kết quả ép kiểu sang __int128 và in bằng hàm tự viết vì cout không in được kiểu này.
Kết quả chấm: đạt 32/32 test
#include <bits/stdc++.h>
using namespace std;
typedef __int128 lint; // BSCNN có thể lên tới 10^20, vượt long long
void inSo(lint x) {
if (x == 0) { cout << 0; return; }
string s;
while (x > 0) { s += char('0' + (int)(x % 10)); x /= 10; }
reverse(s.begin(), s.end());
cout << s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BSCNN.INP", "r")) {
freopen("BSCNN.INP", "r", stdin);
freopen("BSCNN.OUT", "w", stdout);
}
long long a, b;
cin >> a >> b;
// BSCNN(a,b) = a * b / UCLN(a,b); chia trước để tránh tràn số
long long g = __gcd(a, b);
lint bscnn = (lint)(a / g) * b;
inSo(bscnn);
cout << "\n";
return 0;
}
Bình luận