【CQOI2007】余数求和

Description

给定n,k，求$sumlimits_{i=1}^{n}(k mod i)$的值

Solution

这是一道整除分块的模板题。

我们将mod运算拆开，得到$ans=n imes k-sumlimits_{i=1}^{n}(lfloorfrac{k}{i} floor i)$

我们发现，$lfloorfrac{k}{i} floor$的值在某一区间的值的相等的，所以我们可以将这一块集中处理，在[1,n]内大约有$sqrt{k}$块，所以时间复杂度大约为$O(sqrt{k})$

Code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 inline ll read() {
 5     ll ret = 0, op = 1;
 6     char c = getchar();
 7     while (!isdigit(c)) {
 8         if (c == '-') op = -1; 
 9         c = getchar();
10     }
11     while (isdigit(c)) {
12         ret = ret * 10 + c - '0';
13         c = getchar();
14     }
15     return ret * op;
16 }
17 int main() {
18     ll n = read(), k = read();
19     ll ans = n * k;
20     for (register int l = 1, r; l <= n; l = r + 1) {
21         if (k / l == 0) r = n;
22         else r = min(n, k / (k / l));
23         ans -= (r - l + 1) * (k / l) * (l + r) >> 1; 
24     }
25     printf("%lld
", ans);
26     return 0;
27 }

AC Code