除法分块

对于这样一个式子$∑_{i=1}^n\lfloor\frac{n}{i}\rfloor$

朴素的解法是$O(n)$的，但是$\frac{n}{i}$在$i$~$\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$这个范围是相等的。大概存在$2\sqrt{n}$段，证明略（我也不会）。

那么可以写下下面的代码

#include<bits/stdc++.h>
using namespace std;
long long n;
long long ans;
int main(){
    cin>>n;
    ans=0;
    for(int l=1,r;l<=n;l=r+1){
        r=n/l?min(n/(n/l),n):n;
        ans+=(n/l)*(r-l+1);
    }
    cout<<ans;
    return 0;
} 

对于一类我们需要推导

经典例题P2261 [CQOI2007]余数求和

$ans=∑_{i=1}^{n} k\%i$

注意到$k\%i=k-\lfloor\frac{k}{i}\rfloor*i$

所以

$ans=∑_{i=1}^{n}k-\lfloor\frac{k}{i}\rfloor*i$

$=kn-∑_{i=1}^{n}i*\lfloor\frac{k}{i}\rfloor$

于是这个式子我们可以在$\sqrt{n}$内做完，那么这题就做完了

#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long ans;
int main(){
    cin>>n>>k;
    ans=n*k;
    for(int l=1,r;l<=n;l=r+1){
        r=k/l?min(k/(k/l),n):n;
        ans-=(k/l)*(r-l+1)*(l+r)>>1;
    }
    cout<<ans;
    return 0;
}