一句话题意
求 \(\sum_{i=1}^{n} (k ~~\texttt{mod} ~~i)\)
Solution
30分做法：
说实话并不知道怎么办。
60分做法：
很明显直接一遍o(n)枚举 i 就可以求出。
100分做法：
对于每一个k mod i，我们知道k mod i = k-k/i*i，那么
\(\quad \sum_{i=1}^{n}{k \quad mod \quad i}=n*k-\sum_{i=1}^{n}(k/i*i)\)
所以这个题目就转化成了求 \(\sum_{i=1}^{n}(k/i*i)\)。
于是我们很敏锐地察觉到 k/i 貌似有点可操作性 （胡乱BB），因为我们发现对于一段区间的i，k/i 的值是一样的并且是连续的区间，例如：
100/25=100/24=100/23=100/22=100/21=4，因为这一段k/i的值都相等，那么可以一起计算，我们只需要运用等差数列求和公式求出21到25之和，再乘上4便是要求的值。
那么我们定义一个L和R，表示k/i的值相等的区间的两个端点。
首先我们可以知道L=上一次的R+1（区间都是连续的）。
因为L是当前区间中i的最小值，那么最大值就是k/(k/i)。
打个比方：21是100/i=4中最小的i，那么此区间中最大的就是100/4=25。
那么思路就很明显了：
首先Ans=n×k，再减去\(\sum_{i=1}^{n}(k/i*i)\)。
对于公式\(\sum_{i=1}^{n}(k/i*i)\)：
初始值L=1，R=0，然后L=上一个R+1，R=k/(k/L)。
每次Ans-=(k/L)×(R-L+1)×(L+R)/2（等差数列求和，应该都懂）。
直到R=n即可，注意R=min(k/(k/L),n)，以防越界。
时间复杂度 巨说是\(o(\sqrt{n})\)。
Ps:要开long long!!!!
Coding
60分代码
#include <bits/stdc++.h>
using namespace std;
_int main()
{
long long n,k,ans=0;
cin>>n>>k;
for (long long i=1;i<=n;++i)
ans+=(k%i);
cout<<ans;
return 0;
}
100分代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long l,r,n,k,ans;
cin>>n>>k;
ans=n*k;
l=1;
r=0;
while(r<n)
{
if(k/l!=0) r=min(k/(k/l),n);
else r=n;
ans-=(k/l)*(r-l+1)*(l+r)/2;
l=r+1;
}
cout<<ans;
return 0;
}
传说中的极简AC不易懂，233.