思路
数学
数学
非常经典的题目
注意到 \(k \bmod i = k - \lfloor k / i\rfloor * i\)。
于是可以对题目进行转化，从求 \(G(n, k) = \sum_{i = 1}^k n \bmod i\) 变为求 \(G(n, k) = n \times k - \sum_{i = 1}^n\lfloor k/i\rfloor \times i\)，所以仅需求出 \(\sum_{i = 1}^n\lfloor k/i\rfloor \times i\) 即可。
定理一：\(\forall i \in [1, k]\)，\(\lfloor k/i \rfloor\) 仅有 \(2\sqrt k\) 种可能。
证明：若 \(i \leq \sqrt k\)，则 \(\lfloor k/i\rfloor \geq \sqrt k\)，而若 \(i \gt \sqrt k\)，则 \(\lfloor k/i\rfloor \lt \sqrt k\)。
所以 \(\forall i \in [1, k]\)，\(\lfloor k/i\rfloor\) 仅有 \(2\sqrt k\) 种可能。
证毕。
定理二：\(\forall i \in [x, \lfloor k/\lfloor k/x\rfloor\rfloor]\)，\(\lfloor k/i\rfloor\) 相同。
证明：很显然，\(i = \lfloor k/\lfloor k/x\rfloor\rfloor\) 是最大的使 \(k / i = k / x\) 的值，而 \(\lfloor k / i\rfloor\) 随 \(i\) 的增大单调递减，故 \(\forall i \in [x, \lfloor k/\lfloor k/x\rfloor\rfloor]\)，\(\lfloor k/i\rfloor\) 相同。
对于一段 \([x, \lfloor k/\lfloor k/x\rfloor\rfloor]\)，它的贡献为 \(\sum_{i = x}^{\lfloor k/\lfloor k/x\rfloor\rfloor} \lfloor k/x \rfloor \times i\)，这可以用等差数列公式快速求得。
因为仅有 \(2\sqrt k\) 种取值，时间复杂度为 \(O(\sqrt k)\)。
代码
点击查看代码
/*
--------------------------------
| code by FRZ_29 |
| code time |
| 2024/08/20 |
| 17:29:36 |
| 星期二 |
--------------------------------
*/
#include <iostream>
#include <climits>
#include <cstdio>
#include <ctime>
typedef long long LL;
using namespace std;
void RD() {}
template<typename T, typename... U> void RD(T &x, U&... arg) {
x = 0; int f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f; RD(arg...);
}
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)
LL n, k, ans;
int main() {
// freopen("read.in", "r", stdin);
// freopen("out.out", "w", stdout);
// time_t st = clock();
RD(n, k);
ans = n * k;
for (int x = 1, gx; x <= n; x = gx + 1) {
gx = k / x ? min(k / (k / x), n) : n;
ans -= (k / x) * (x + gx) * (gx - x + 1) / 2;
}
printf("%lld", ans);
// printf("\n%dms", clock() - st);
return 0;
}
/* ps:FRZ弱爆了 */
一片春愁待酒浇。江上舟摇，楼上帘招。秋娘渡与泰娘桥，风又飘飘，雨又萧萧。
何日归家洗客袍？银字笙调，心字香烧。流光容易把人抛，红了樱桃，绿了芭蕉。