数论分块复习

· · 个人记录

数论分块复习

形如：

\sum_{i=1}^n{\left \lfloor \frac{n}{i} \right \rfloor}

可以在 \sqrt n 的时间内求出：

for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l);
    ans+=(r-l+1)*(n/l);
}

如果不是裸的式子，可以先预处理前缀和来做（这就用得到杜教筛了）

例题：P1829

先用莫比乌斯处理。

对于式子

\sum_{k=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\mu{(k)}}k^2 (\sum_{p=1}^{\left \lfloor \frac{n}{d*k} \right \rfloor}p)({\sum_{q=1}^{\left \lfloor \frac{n}{d*k} \right \rfloor}}{q})

我们可以用数论分块来做

res=(res+( (sum[r]-sum[l-1]) * ((x/l+1)*(x/l)/2) * ((y/l+1)*(y/l)/2);

例题：P2260 模积和

求：

\sum_{i=1}^n{\sum_{j=1}^m(n \bmod i)*(m \bmod j),(i \ne j)}

解：

\begin{aligned}\\ & \sum_{i=1}^n{\sum_{j=1}^m(n \bmod i)*(m \bmod j),(i \ne j)}\\ & =\sum_{i=1}^n{\sum_{j=1}^m{(n \bmod i)*(m \bmod j)}}-\sum_{i=1}^n{(n \bmod i)*(m \bmod i)} \\ \end{aligned}

考虑前面半段：

\begin{aligned}\\ & [\sum_{i=1}^n(n \bmod i)] * [\sum_{j=1}^m(m \bmod j)]\\ & =[\sum_{i=1}^n{(n-i* \left \lfloor \frac{n}{i} \right \rfloor}] * [\sum_{j=1}^m{(m-j* \left \lfloor \frac{m}{j} \right \rfloor}] \\ & =[n^2-\sum_{i=1}^n{(i* \left \lfloor \frac{n}{i} \right \rfloor})] * [m^2-\sum_{j=1}^m{(j* \left \lfloor \frac{m}{j} \right \rfloor})] \\ & \end{aligned}

然后这个式子就是一个整除分块的式子了，“维护”出 i 的前缀和，然后走流程即可。

    int ans1=n*n%modn;
    for(int l=1;l<=n;l=r+1)
    {
        r=(n/(n/l));
        ans1=(ans1 - get_sum(l,r)*(n/l)%modn + modn)%modn;//get_sum 就是求 sigma(l,r);
    }

考虑后半段：

\begin{aligned}\\ & \sum_{i=1}^n{(n \bmod i)*(m \bmod i)}\\ & =\sum_{i=1}^n[(n-i*\left \lfloor \frac{n}{i} \right \rfloor)*(m-i*\left \lfloor \frac{m}{i} \right \rfloor)]\\ & =\sum_{i=1}^n{(nm-n*i*\left \lfloor \frac{m}{i} \right \rfloor-m*i*\left \lfloor \frac{n}{i} \right \rfloor+i^2*\left \lfloor \frac{n}{i} \right \rfloor\left \lfloor \frac{m}{i} \right \rfloor)}\\ & =n^2m-n\sum_{i=1}^n{i*\left \lfloor \frac{m}{i} \right \rfloor}-m\sum_{i=1}^n{i*\left \lfloor \frac{n}{i} \right \rfloor}+\sum_{i=1}^n{i^2*\left \lfloor \frac{n}{i} \right \rfloor\left \lfloor \frac{m}{i} \right \rfloor}\\ & \end{aligned}

注意数论分块的时候最好 r=min(n,n/(n/l)),这样子不会越界。（加就完事了，也不吃亏）

#include<bits/stdc++.h>

using namespace std;

const int MX=1*1000+100;
#define LL long long
#define inf 0x3f3f3f3f

#define modn 19940417

inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

LL n,m;

const LL inv2=9970209;
const LL inv6=3323403;

inline LL get_sum(LL l,LL r)
{
    return (r+l)*(r-l+1)%modn*inv2%modn;
}

inline LL get_pf(LL l,LL r)
{
    return ( ( r*(r+1)%modn*(2*r%modn+1)%modn*inv6%modn ) - ( (l-1)*(l)%modn*(2*l%modn-1)%modn*inv6%modn ) +modn )%modn;
}

LL bans,cans;

int main(int argc, char const *argv[])
{
    //printf("%lld\n",get_pf(114514,1919810));
    n=read(),m=read();
    if(n>m) swap(n,m);
    LL ans1=n*n%modn;
    for(LL l=1,r;l<=n;l=r+1)
    {
        r=(n/(n/l));
        ans1=(ans1 - get_sum(l,r)*(n/l)%modn + modn)%modn;
    }
    LL ans2=m*m%modn;
    for(LL l=1,r;l<=m;l=r+1)
    {
        r=(m/(m/l));
        ans2=(ans2 - get_sum(l,r)*(m/l)%modn + modn)%modn;
    }
    bans=ans1*ans2%modn;
    //cout<<bans<<endl;

    cans=(n*n%modn*m)%modn;
    LL now=0;
    for(LL l=1,r;l<=n;l=r+1)
    {
        r=min(n,(m/(m/l)));
        now=(now + get_sum(l,r)*(m/l)%modn )%modn;
    }
    now=(now*n)%modn;
    cans=(cans-now+modn)%modn;

    now=0;
    for(LL l=1,r;l<=n;l=r+1)
    {
        r=min(n,(n/(n/l)));
        now=(now + get_sum(l,r)*(n/l)%modn )%modn;
    }
    now=(now*m)%modn;
    cans=(cans-now+modn)%modn;

    now=0;
    for(LL l=1,r;l<=n;l=r+1)
    {
        r=min(n,min( (n/(n/l)) , (m/(m/l)) ));
        now=(now + get_pf(l,r)*(n/l)%modn*(m/l)%modn );
    }
    cans=(cans+now)%modn;

    bans=(bans-cans+modn)%modn;
    cout<<bans<<endl;
    return 0;
}

洛谷太逊了，公式有问题，直接复制到 Typora 里去看

updata:洛谷又不逊了。