Để có thể làm bài này, ta cần có 1 nhận xét:
***Với mỗi số i sao cho n/a = b, thì chuỗi chia dư của nó tạo thành 1 dãy giảm dần với khoảng cách là b.***
Ví dụ: với __n = 20__, thì khi __a = {7, 8, 9, 10}__ thì __b = 2__, khi đó các n%a lần lượt là __{6, 4, 2, 0}__
Quan sát ta có thể thấy dãy trên hoàn toàn đúng với nhận xét vừa rồi, nhưng tại sao lại như vậy?
Ta có $$ n = a \cdot b + r $$
Đặt:$$ r_1 = r - k; $$
$$ n = a \cdot b + r_1 + b$$
$$
n = (a + 1) \cdot b + r_1
$$
Khi này n và b là cố định nên khi a tăng 1 đơn vị, thì r sẽ giảm b đơn vị
Vậy nên việc của chúng ta chỉ là chia đoạn từ 1 đến n thành các đoạn sao cho mỗi giá trị a trong đoạn đó thì n/a cố định (=b).
Câu hỏi ở đây là chúng ta có bao nhiêu đoạn được tạo ra???
Đáp án ở đây chỉ có khoảng 2√(n).
Ta sẽ xét các giá trị a từ 1 đến √(n).
Với a = 1 thì b = n;
a = 2 thì b = n/2
Điều này có nghĩa là với giá trị a từ n đến n/2+1 thì b = 1.
Tương tự với các giá trị khác thì đến khi a = √(n) thì khi đó ta đã có được khoảng √(n) đoạn tương ứng.
Tương tự khi a = √(n) + 1 đến n.
Vậy ta sẽ có được khoảng 2√(n) đoạn.
Khi có giá trị đầu và cuối của 1 dãy quy luật, nếu bạn đã học qua lớp 6 thì bạn sẽ biết đến công thức:
$$\frac{(r+l)\cdot(n)}{2}$$
Với l, r là giá trị đầu tiên, cuối cùng của dãy, n là số lượng phần tử. Lấy vị dụ đầu tiên, bạn sẽ thấy
$$\frac{(6+0)\cdot(4)}{2} = 0 + 2 + 4 + 6 = 12$$
Việc cuối cùng chỉ là code thôi.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD = 1e9 + 7;
ll n, m, l, r, d, id, sum = 0, pre, suf, lim;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr)
cin >> n >> m;
lim = min(n, m);
r = 0;
while(r < lim){
l = r + 1;
id = n / l;
r = min(n / id, lim);
d = r - l + 1;
pre = n % l;
suf = n % r;
d %= MOD;
sum = (sum + (((suf + pre) % MOD * d) % MOD * 500000004ll) % MOD) % MOD;
}
cout <<(sum + ((max(0ll, m - n) % MOD) * (n % MOD)) % MOD) % MOD;
return 0;
}
Trong đó 500000004 = 2^-1 mod(1e9+7)
nhanmuaairi
Created at
1 likes