Hướng dẫn giải của CAU3
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
Với N cho trước, cần tìm m < N sao cho N chia m có số dư lớn nhất. Quan sát: số dư lớn nhất có thể đạt là floor((N-1)/2) và đạt khi m = floor(N/2) + 1 (với N ≥ 5 thì m này là duy nhất).
Sub 1: Vét cạn thử mọi m — ~O(N)~
Thử lần lượt mọi m từ 1 đến N-1, tính N mod m và giữ m cho số dư lớn nhất. Đúng với mọi N nhưng quá chậm khi N lên tới 10^18; đã kiểm tra đúng ở subtask 1 (N ≤ 10^4, T ≤ 10) bằng so sánh ngẫu nhiên với lời giải đầy đủ.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long N;
cin >> N;
// Vét cạn: thử mọi m từ 1 đến N-1, giữ m cho N mod m lớn nhất
long long bestM = 1, bestR = -1;
for (long long m = 1; m < N; m++) {
long long r = N % m;
if (r > bestR) {
bestR = r;
bestM = m;
}
}
cout << bestM << "\n";
}
return 0;
}
Sub 2: Công thức m = N/2 + 1 — ~O(1)~
Đáp số là N/2 + 1 (chia nguyên). Ví dụ N = 6 cho 4 (6 mod 4 = 2), N = 9 cho 5 (9 mod 5 = 4). Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long N;
cin >> N;
// Với N >= 5, số dư lớn nhất đạt được khi Xmod = N/2 + 1
// (khi đó N mod Xmod = N - N/2 - 1, và không có m nào khác cho dư lớn hơn)
cout << N / 2 + 1 << "\n";
}
return 0;
}
Bình luận