题目大意
求
\[\sum_{i=1}^{n}(k\mod i)\]\(n,k\leq 10^9\)。题解
先只考虑\(n\leq k\)的情况。
\[\sum_{i=1}^{n}(k\mod i)=\sum_{i=1}^{n}k-i\lfloor \frac{k}{i}\rfloor=kn-\sum_{i=1}^{n}i\lfloor \frac{k}{i}\rfloor\] 看到\[\sum_{i=1}^{n}\lfloor \frac{k}{i}\rfloor\] 则想到整除分块。整除分块
结论：
\[\lfloor \frac{k}{i}\rfloor=\lfloor\frac{k}{\lfloor\frac{k}{\lfloor\frac{k}{i}\rfloor}\rfloor}\rfloor\]
规律
当\(\lfloor\frac{k}{\lfloor\frac{k}{i}\rfloor}\rfloor\)一定时，所有满足上式的\(i\)都在一段连续的区间内（组成了一块），区间右端点是\(\lfloor\frac{k}{\lfloor\frac{k}{i}\rfloor}\rfloor\)。
因此操作时，直接对一块进行统一操作即可。数学推导
令一块的左端点为\(l\)，右端点为\(r\)，\(v=\frac{k}{r}\)，我们现在要求一块内的和
\[\sum_{i=l}^{r}iv=\sum_{i=0}^{r-l}v(l+i)=v\sum_{i=0}^{r-l}(l+i)\] 此时注意：和式中运算的次数为\(r-l-0+1=r-l+1\)，而不是\(r-l\)。所以接下来\[原式\neq v(l(r-l)+\sum_{i=0}^{r-l}i)\]\[原式=v(l(r-l+1)+\sum_{i=0}^{r-l}i)\] 在这里错了就完了！ 最终运用等差数列的知识得到\[原式=\frac{v(r+l)(r-l+1)}{2}\] 把所有的上式加起来再被\(nk\)一减即可。注意
边界条件：赋值\(r\)时，它不能直接等于\(\lfloor\frac{k}{\lfloor\frac{k}{i}\rfloor}\rfloor\)，而应当是它和\(n\)的较小值。另外还要考虑\(\lfloor\frac{k}{i}\rfloor=0\)的情况。
对于\(n>k\)的情况，把额外值加上即可。要明确\(n-k\)以及\(k\)的含义呀！#include#include #include #include using namespace std;#define ll long longint main(){ ll n, k; scanf("%lld%lld", &n, &k); ll ans = 0, extra = 0; if (n > k) { extra = (n - k) * k; n = k; } for (ll l = 1, r; l <= n; l = r + 1) { int divVal; r = (divVal = k / l) ? min(n, k / (k / l)) : n; ans += divVal * ((r - l + 1) * (l + r) / 2); assert(ans > 0); } printf("%lld\n", n * k - ans + extra); return 0;}