标题也许叫整除分块吧

求\(1\)到\(n\)因数的个数\(\sum_{i=1}^n(\sum_{d|n}1)\)

范围\(1e14\)时限3s

\(n\sqrt{n}\)的暴力铁定gg

分开考虑

\(1\)到\(n\)中含有\(1\)因数的个数有\(n/1\)个

含有2因数的个数有\(n/2\)个**

······

含有n因数的个数有\(n/n\)个

问题就转化为求\(\sum_{i=1}^{n}[\frac{n}{i}]\)

然后我们就可以把\(O(n\sqrt{n})\)的暴力转化为\(O(n)\)了

可还是过不了&1e14的数据&

我们发现，我们求得\(\frac{n}{i}\)在一段区间内是连续的

而且呈现单调递减，这样我们就可以开心的套用二分啦

那到底有多少段连续的区间

把i分开考虑

1到\(\sqrt{n}\)之内,if都不同撑死有\(\sqrt{n}\)段

\(\sqrt{n}\)到n之内,求\(\frac{n}{i}\)连续的一段,取值范围为1到\(\sqrt{n}\)之内,撑死也有\(\sqrt{n}\)个

区间个数是\(\sqrt{n}\)级别的，二分是\(log\)级别的

所以复杂度为\(O(\sqrt{n}logn)\)

**一直以为这是根号的%>_<%**

参见牛客练习赛25(1e9)

#include <bits/stdc++.h>
using namespace std;
long long ans;
int l,n;
int main() {
    int q;
    cin>>q;
    while(q--) {
        cin>>n;
        l=1;
        ans=0;
        for(int i=1; i<=n; ++i) {
            int r=n;
            int mid=(l+r)>>1;
            while(n/l!=n/r) {
                mid=(l+r)>>1;
                r=mid;
            }
            ans+=n/l*(r-l+1);
            if(r==n) break;
            l=r+1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

直到我遇到了这个题luogu3935以及评测80sTLE的惨痛

才发现我是个zz诶

当我们知道\(l\)的时候，也就是一段的开头，如何快速找到我们要的r呢
\(n/l\)是\(n\)中含有\(t=n/l\)块完整的\(l\)
那么\(n/t\)便是有\(t\)块最大的数，便是我们要求的\(r\)
所以\(r=n/(n/l)\)
所以我们求块的时间由二分的\(O(logn)\)变为了\(O(1)\)
复杂度为\(O(\sqrt{n})\)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll solve(ll n)
{
    ll ans=0;
    for(ll l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        ans+=(r-l+1)%mod*(n/l)%mod;
        ans%=mod;
    }
    return ans;
}
int main() 
{
    ll x,y;
    cin>>x>>y;
    cout<<((solve(y)-solve(x-1))%mod+mod)%mod;
    return 0;
}

http://www.cnblogs.com/1000Suns/p/9193713.html