一、应用情景
求 \(\sum\limits_{i = 1}^{n} g(i)\lfloor\frac n i\rfloor,n\leq 10 ^{12}\)
二、常见结合
- 莫比乌斯反演
- ……
三、算法原理&代码实现
实际上，\(~\lfloor \frac n i\rfloor~\)的取值其实最多只有\(~2\times\sqrt n~\) 种：
对于\(~i\in [1,\sqrt n]~\)：只有\(~\sqrt n~\)个
对于\(~i\in[\sqrt n,n]~\)：\(~\lfloor \frac n i\rfloor~\)只有\(\sqrt n\)个
我们对于每一种取值，算出该种取值区间的 \(g(i)\) 的和，即可求出答案
通常地，为了求解 \(g(i)\) 我们通常会预处理前缀和，在数论分块的时候就可以 \(O(1)\) 求解了
时间复杂度：\(~O(\sqrt n)~\)
code:
void solve(){
scanf("%lld",&n);
ll ans = 0;
for(int i = 1,j,num; i <= n; i = j + 1){
num = n / i;
j = n / num;
ans += 1ll * num * (j - i + 1);
}
printf("%lld\n",ans);
return;
}
五、练习
① UVA11526 H(n)
题意
求解：
\[\sum_{i=1}^{n} \lfloor \frac n i \rfloor \]题解
板子，只不过你需要注意当 \(n = 2147482647\) 时，\(for\) 循环的 \(i\) 有可能溢出，然后导致 RE/TLE 帖子
② CQOI2007 余数求和
求解：\(~G(n,k)=\sum\limits_{i=1}^nk~mod~i~\)
solution：
\(~G(n,k)=\sum\limits_{i=1}^nk~mod~i~\)
\(~G(n,k)=\sum\limits_{i=1}^n(k - i \times \lfloor \frac k i\rfloor)~\)
\(~G(n,k)=n\times k - \sum\limits_{i=1}^ni \times \lfloor \frac k i\rfloor~\)
还是数论分块，只不过将(j - i + 1)改为(i + j) * (j - i + 1) / 2即可