Hướng dẫn giải của SỐ ĐẶC BIỆT
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
Số ~K~ là đặc biệt khi ~K^2 - 1~ chia hết cho 5, tức ~K \equiv 1~ hoặc ~K \equiv 4 \pmod 5~. Đáp án là số các ~K~ đặc biệt trong đoạn ~[L, R]~.
Sub 1: Vét cạn — ~O(R - L)~, dùng khi ~R \le 10^6~
Duyệt từng ~K~ trong ~[L, R]~ và kiểm tra ~(K^2 - 1) \bmod 5 = 0~.
Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 2: Đếm bằng công thức — ~O(1)~
Đếm số có dạng ~K \equiv 1, 4 \pmod 5~ trong ~[1, x]~ bằng ~f(x) = 2 \lfloor x/5 \rfloor + [x \bmod 5 \ge 1] + [x \bmod 5 \ge 4]~. Đáp án là ~f(R) - f(L-1)~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đọc ~L, R~ từ tệp CAU1.INP và ghi kết quả vào CAU1.OUT. Dữ liệu ~R \le 10^6~ dùng sub 1, còn lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
long long L, R;
// Sub 1: vet can, duyet tung K trong [L, R] kiem tra K^2 - 1 chia het cho 5. Dung khi R <= 10^6.
void sub1() {
long long cnt = 0;
for (long long k = L; k <= R; k++)
if ((k * k - 1) % 5 == 0) cnt++;
cout << cnt << "\n";
}
// Dem so K trong [1, x] co K chia 5 du 1 hoac 4 (K^2 chia 5 du 1 khi K = 1 hoac 4 mod 5).
// Moi chu ky 5 co 2 so; phan du r con lai dem them.
long long f(long long x) {
if (x <= 0) return 0;
long long q = x / 5, r = x % 5;
long long c = 2 * q;
if (r >= 1) c++; // du 1
if (r >= 4) c++; // du 4
return c;
}
// Sub 2: cong thuc O(1), dung cho R lon.
void sub2() {
cout << f(R) - f(L - 1) << "\n";
}
int main() {
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
cin >> L >> R;
if (R <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận