1. 题目

传送门=￣ω￣=

题意：
给出 n,k，求：
$$\sum_{i=1}^{n}k\ mod\ i$$
$$n,k\in [1,10^9]$$

2. 题解

以我这智障脑袋都想得出的题。。。
$$k\ mod\ i=k-\left \lfloor k\div i\right \rfloor \times i$$
所以：
$$\sum_{i=1}^{n}k\ mod\ i$$
就等于：
$$\sum_{i=1}^{n}k-\left \lfloor k\div i\right \rfloor \times i$$
等于：
$$n\times k-\sum_{i=1}^{n}\left \lfloor k\div i\right \rfloor \times i$$

那么答案很显然了，$\left \lfloor k\div i\right \rfloor$的值当 i 在一定范围内是相同的。
那我们把这个值相同的 i 放在同一个块中，设当前块的首部的 i 的值为 a，尾部的 i 的值为 b，这一块所有的 $\left \lfloor k\div i\right \rfloor$的值都为 c，那么显然这一块的总和为：
$$c\times (a+b)\times (b-a+1)\div 2$$
其中 $(a+b)\times (b-a+1)\div 2$就是个等差数列求和公式，因为这一块的首部为 a，尾部为 b，元素个数为 b-a+1，且前一项比后一项大 1
然后我们一块块求出每一块的总和，加起来就得到了 $$\sum_{i=1}^{n}\left \lfloor k\div i\right \rfloor \times i$$的值，用 n×k 减去这个值就行了

求每块的值的复杂度是 O(1) 的，然后共有 $\sqrt{n}$块，复杂度为 $\sqrt{n}$。

注意计算出的块尾可能超过 n，要特判（即块尾=min(块尾,n））
还有，如果n>k 的话是没有意义的，直接把 n 强行改为 k 即可

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,k,ans;
int main()
{
  scanf("%lld%lld",&n,&k),ans=n*k;
  if(n>k)n=k;
  for(LL i=1,j;i<=n;i=j+1)
    j=min(k/(k/i),n),ans-=((k/i)*(i+j)*(j-i+1))>>1;
  printf("%lld\n",ans);
  return 0;
}