数论分块及应用

在一类要统计∑f(i) (1<=i<=n)的数学题中，由于f(i)是单调的，故存在x,y∈[i,j]使得f(x)=f(y)。于是只要找到这段区间就可以节省计算区间内每一个函数值的时间开销。
时间复杂度大抵是O(sqrt(n))的。

牛客——美味果冻：
题解

#include <bits/stdc++.h>
using namespace std;
const int N=3000010;
const int mod=1e9+7;
int p[N];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        long long ans=0;
        for(int i=0;i<=n;i++)
            p[i]=1;
        for(int j=1;j<=n;j++)
        {
            int maxn=n/j,left=j,right=2*j-1;
            for(int i=1;i<maxn;i++)
            {
                p[i]=1LL*p[i]*i%mod;
                ans=(ans+(1LL*(left+right)*j/2)%mod*p[i])%mod;
                left+=j;
                right+=j;
            }
            p[maxn]=1LL*p[maxn]*maxn%mod;
            ans=(ans+((1LL*(left+n)*(n-left+1)/2)%mod)*p[maxn])%mod;
        }
        printf("%lld\n",ans%mod);
    }
    return 0;
}

bzoj 1968: [Ahoi2005]COMMON 约数研究
【整除分块】：详解
直接暴力分块，O(n)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        long long ans=0;
        for(int i=1;i<=n;i++)
            ans+=(n/i);
        printf("%lld\n",ans);
    }
    return 0;
}

但这样并没有体现分块的优点。对于上述的程序，我们可以发现，(n/i)对于不同的i值，其值可以是相同的，因此，如果可以直接计算出对于每个(n/i),有多少个i的值是相同的，既可以减少减少次数。
因此可以有以下优化，复杂度为O(sqrt(n))。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        long long ans=0;
        int l=1,r=1;
        for(int i=1;i<=n;i++)
        {
            r=n/(n/i);
            if(r>n)
                r=n;
            ans+=((r-l+1)*(n/i));
            l=r+1;
            i=r;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

bzoj 2956: 模积和

分别把前后的括号拆开，任何利用分块求。求逆元，及以下公式（挺常用）。
相乘一定注意取模。

另外，19940417不是素数！

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=19940417;
ll solve(ll num,ll up)
{
    ll l=1,r=1,res=0;
    for(ll i=1;i<=up;i=r+1)
    {
        r=min(num/(num/i),up);
        //ll t=(((l+r)%mod*(r-l+1)%mod)*(9970209%mod))%mod;
        res=(res+(num/i)*(l+r)%mod*(r-l+1)%mod*9970209%mod)%mod;
        l=r+1;
    }
    return res%mod;
}
ll sum(ll x)
{
    return x*(x+1)%mod*(2*x+1)%mod*3323403%mod;
}
ll f(ll k,ll n,ll m)
{
    ll res=0,l=1,r=1;
    for(ll i=1;i<=k;i=r+1)
    {
        r=min(k,min(n/(n/i),m/(m/i)));
        //ll t=(sum(r)-sum(l-1))%mod;
        res=(res+(sum(r)-sum(l-1))%mod*(n/i)%mod*(m/i)%mod)%mod;
        l=r+1;
    }
    return res%mod;
}
int main()
{
    ll n,m;
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        ll ans=((n*n-solve(n,n))%mod*((m*m-solve(m,m))%mod)%mod)%mod;//cout<<"ans="<<ans<<endl;
        ll k=min(n,m);
        ans=(ans-(k*n%mod*m))%mod;//cout<<"ans="<<ans<<endl;
        ans=(ans+m*solve(n,k)%mod+n*solve(m,k)%mod)%mod;//cout<<"ans="<<ans<<endl;
        ans=ans-f(k,n,m);//cout<<"ans="<<ans<<endl;
        while(ans<0)
            ans+=mod;
        printf("%lld\n",ans%mod);
    }
    return 0;
}