Hướng dẫn giải của Bé làm toán (đề Hòa Bình 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
Dãy vô hạn gồm 1 số 1, 2 số 2, 3 số 3, ... Cần tính tổng các số ở vị trí từ ~A~ đến ~B~ (~B \le 10^9~), lấy dư ~10^9+7~. Đặt ~S(m)~ là tổng ~m~ số đầu tiên thì đáp án là ~S(B) - S(A-1)~.
Sub 1: Tạo dãy tường minh — ~O(B)~, dùng khi ~B \le 10^5~
Sinh dãy đến vị trí ~B~ rồi cộng từ vị trí ~A~ đến ~B~. Nếu chỉ nộp sub này: đúng 27/30 test (3 test lớn không chạy kịp).
Sub 2: Cộng theo nhóm — ~O(\sqrt{B})~
Nhóm thứ ~k~ gồm ~k~ số ~k~, nên đến vị trí ~B~ chỉ có khoảng ~\sqrt{2B}~ nhóm (tối đa khoảng 45000). Với mỗi nhóm cộng ~\min(k, \text{số vị trí còn lại}) \cdot k~, lấy dư sau mỗi phép nhân. Đáp án ~(S(B) - S(A-1)) \bmod (10^9+7)~, nhớ cộng thêm ~10^9+7~ nếu âm. Nộp riêng sub này đúng 30/30 test.
Chương trình hoàn chỉnh
Hàm ~main~ đọc ~A, B~; nếu ~B \le 10^5~ gọi sub1, ngược lại gọi sub2. 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. Chương trình đạt 30/30 test.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long A, B;
// S(m) = tổng m số đầu tiên của dãy 1,2,2,3,3,3,... theo cách tính từng nhóm (không mod trong phép nhân lớn)
long long prefixSum(long long m) {
long long res = 0, k = 1;
while (m > 0) { // nhóm k gồm k số k; số lượng chạy theo căn m
long long take = min(k, m);
res = (res + (take % MOD) * (k % MOD)) % MOD;
m -= take;
k++;
}
return res;
}
// Sub 1: tạo dãy tường minh đến vị trí B rồi cộng từ A đến B, O(B), dùng khi B <= 10^5
void sub1() {
vector<int> v;
v.push_back(0); // chỉ số từ 1
for (int k = 1; (long long)v.size() <= B; k++)
for (int j = 0; j < k && (long long)v.size() <= B; j++) v.push_back(k);
long long s = 0;
for (long long i = A; i <= B; i++) s += v[i];
cout << s % MOD << "\n";
}
// Sub 2: tổng tiền tố S(B) - S(A-1), mỗi S duyệt các nhóm, chỉ ~sqrt(2B) nhóm: O(sqrt(B))
void sub2() {
long long ans = ((prefixSum(B) - prefixSum(A - 1)) % MOD + MOD) % MOD;
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> A >> B;
if (B <= 100000) sub1();
else sub2();
return 0;
}
Bình luận