P2261 - Description
给出正整数 \(n\) 和 \(k\)，请计算
\[G(n,k)=\sum_{i=1}^n k\mod i
\]
\(1\le n.k\le 10^9\)。
P2261 - Solution
首先很自然地把 \(k\mod i\) 转化为 \(k-i\times \lfloor \frac{k}{i}\rfloor\)。再把每次不变的 \(k\) 移到 \(\sum\) 外面去，就得到了
\[G(n,k)=n\times k-\sum_{i=1}^n \lfloor \frac{k}{i} \rfloor\times i
\]
式子可以直接整除分块搞。
记当前块的左端点为 \(l\)，右端点为 \(r\)。由于 \(\left [ l,r\right ]\) 内所有数的 \(\lfloor \frac{k}{i} \rfloor\) 都是相等的，因此当前块对答案的贡献为：
\[\begin{align}
\sum_{i=l}^r \lfloor \frac{k}{i} \rfloor\times i &=\sum_{i=l}^r \lfloor \frac{k}{l} \rfloor\times i\\
&=\lfloor \frac{k}{l} \rfloor\times\sum_{i=l}^r i\\
&=\lfloor \frac{k}{l} \rfloor\times \frac{(l+r)\times (r-l+1)}{2}
\end{align}
\]
可以 \(O(1)\) 计算。
总复杂度为 \(O(\sqrt{n})\)，可以通过。
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,k,ans;
inline int getsum(int l,int r){return (l+r)*(r-l+1)/2;
}
signed main(){cin>>n>>k;ans=n*k;int r=1;for(int l=1;l<=n;l=r+1){if(l>k){break;}r=k/(k/l);if(r>n){r=n;}ans-=getsum(l,r)*(k/l);
// cout<<l<<" "<<r<<endl;}cout<<ans<<endl;return 0;
}