Hướng dẫn giải của Tết ở trường (Đề HSG Quảng Ninh 2021)
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
Đếm số cặp ~(x, y)~ với ~0 \le x \le a~, ~0 \le y \le b~, ~x + y > 0~ và ~x + y~ chia hết cho ~n~. Nhận xét chính: chỉ cần xét các tổng ~s = k \cdot n~ (~k \ge 1~) rồi đếm số cặp có tổng đúng bằng ~s~.
Sub 1: Vét cạn — ~O(a \cdot b)~, dùng khi ~a, b \le 10^3~
Duyệt mọi cặp ~(x, y)~, kiểm tra ~x + y > 0~ và chia hết cho ~n~. Nếu chỉ nộp sub này: đúng 10/25 test.
Sub 2: Duyệt các bội của n — ~O((a+b)/n)~
Với mỗi ~s = n, 2n, \dots \le a + b~, số cặp có tổng ~s~ bằng số ~x~ trong đoạn ~[\max(0, s-b), \min(a, s)]~ (khi đoạn không rỗng). Nếu chỉ nộp sub này: đúng 25/25 test.
Sub 3: Công thức ~O(1)~
Giả sử ~A = \min(a,b)~, ~B = \max(a,b)~, ~T = A + B~. Số cặp có tổng ~s~ là ~s+1~ nếu ~s \le A~; ~A+1~ nếu ~A < s \le B~; ~T-s+1~ nếu ~s > B~. Cộng theo ba đoạn các bội của ~n~ bằng công thức tổng cấp số cộng. Chú ý đáp án có thể tới ~10^{18}~ nên dùng số 128 bit cho phép tính trung gian. Nếu chỉ nộp sub này: đúng 25/25 test.
Chương trình hoàn chỉnh
Main đọc ~n, a, b~ từ file new.inp, nếu ~a, b \le 10^3~ gọi sub1, nếu số bội ~(a+b)/n~ vừa phải thì gọi sub2, ngược lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long n, a, b;
// Sub 1: vét cạn mọi cặp (x, y) — dùng khi a, b <= 1000, O(a*b)
void sub1() {
long long cnt = 0;
for (long long x = 0; x <= a; x++)
for (long long y = 0; y <= b; y++)
if (x + y > 0 && (x + y) % n == 0) cnt++;
printf("%lld\n", cnt);
}
// Sub 2: duyệt tổng s = k*n; với mỗi tổng đếm số x trong [max(0,s-b), min(a,s)]
// Độ phức tạp O((a+b)/n) — dùng khi (a+b)/n không quá lớn
void sub2() {
long long cnt = 0;
for (long long s = n; s <= a + b; s += n) {
long long lo = max(0LL, s - b), hi = min(a, s);
if (hi >= lo) cnt += hi - lo + 1;
}
printf("%lld\n", cnt);
}
// Sub 3: công thức O(1). Giả sử A <= B, T = A + B.
// Số cặp có tổng s: s+1 nếu s <= A; A+1 nếu A < s <= B; T-s+1 nếu s > B.
// Cộng theo từng đoạn các bội của n bằng công thức tổng cấp số cộng.
void sub3() {
typedef __int128 LL;
LL A = min(a, b), B = max(a, b), T = A + B, N = n;
LL res = 0;
LL m1 = A / N; // các k = 1..m1 có s <= A
res += N * m1 * (m1 + 1) / 2 + m1;
LL k1 = A / N + 1, k2 = B / N; // A < s <= B
if (k2 >= k1) res += (k2 - k1 + 1) * (A + 1);
LL k3 = B / N + 1, k4 = T / N; // B < s <= T
if (k4 >= k3) {
LL c = k4 - k3 + 1;
res += c * (T + 1) - N * (k3 + k4) * c / 2;
}
printf("%lld\n", (long long)res);
}
int main() {
freopen("new.inp", "r", stdin);
freopen("new.out", "w", stdout);
scanf("%lld %lld %lld", &n, &a, &b);
if (a <= 1000 && b <= 1000) sub1();
else if ((a + b) / n <= 10000000) sub2();
else sub3();
return 0;
}
Bình luận