Hướng dẫn giải của Bài toán mảnh ghép (đề Trà Vinh 2021)
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ìa hình chữ nhật a × b được cắt thành các hình vuông bằng nhau, không thừa mảnh nào, thì cạnh hình vuông phải là ước chung của a và b. Đề hỏi cạnh lớn nhất, nên đáp số là ƯCLN(a, b).
Sub 1: Thử từ lớn xuống nhỏ — ~O(\min(a, b))~
Thử các độ dài d = min(a, b), min(a, b) − 1, ..., 1; d đầu tiên chia hết cả a và b là đáp số.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
cin >> a >> b;
// Vét cạn: thử mọi độ dài cạnh d từ lớn xuống nhỏ, d là ước chung của a và b thì dừng
long long d = min(a, b);
while (d > 1 && !(a % d == 0 && b % d == 0)) d--;
cout << d << "\n";
return 0;
}
Sub 2: Thuật toán Euclid — ~O(\log \min(a, b))~
Lặp lấy số dư: (a, b) ← (b, a mod b) cho đến khi b = 0, khi đó a là ƯCLN.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b;
cin >> a >> b;
// Cạnh hình vuông lớn nhất cắt hết tấm bìa là ƯCLN(a, b), tính bằng thuật toán Euclid
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
cout << a << "\n";
return 0;
}
Bình luận