数论分块学习笔记

cfkk · 2025-07-28 15:24:59 · 算法·理论

0.前言：老师上课讲了好多，感觉只会这个啊/kk

1.定义：

数论分块可以快速计算一些含有除法向下取整的式子（即形如 \sum^n_{i=1}\lfloor\frac{n}{i}\rfloor 的和式）。当可以在 O(1) 计算 f(r)-f(l) 或已处理出 f 的前缀和时，数论分块就可以在 O(\sqrt{n}) 的时间内计算上述和式的值。 ——摘自 OI Wiki

2.例题：

P1403 [AHOI2005] 约数研究

大致题意：给你一个整数 n，问 \displaystyle\sum^n_{i=1}\displaystyle\sum_{j|i}

考虑进行转化：将枚举每个数的因子转化为枚举倍数，所以原式就变成 \displaystyle\sum^n_{i=1}\lfloor\frac{n}{i}\rfloor 按照模板分块即可，时间复杂度 O(2\sqrt{n})。

代码：

signed main() 
{
    int n=read();
    int cnt=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        cnt+=(n/l)*(r-l+1);
    }
    print(cnt);
    return 0;
}

P2261 [CQOI2007] 余数求和

题目大意：给你两个整数 n 和 k，问\displaystyle\sum^n_{i=1} k \mod i

思路：对于取模，我们可以进行以下转化：a\mod b=a-b\times\lfloor\frac{a}{b}\rfloor。

因此

对最后求和的式子我们可以进行数论分块，时间复杂度 O(\sqrt{k})

代码：

signed main()
{
    int n=read(),k=read();
    int sum=n*k;
    int l,r;
    for(l=1;l<=n;l=r+1)
    {
        if(k/l==0)break;
        r=min(k/(k/l),n);
        sum-=(k/l)*(r-l+1)*(l+r)/2;
    }
    print(sum);
    return 0;
}

P2424 约数和

（感觉这题和第一题很像啊，不懂为什么难度相差怎么大）

大致题意：给你两个整数 l,r，问 \displaystyle\sum^r_{i=l}\displaystyle\sum_{j|i}

思路：和第一题相同，可以用数论分块分别求出 1 到 l 和 1 到 r 的约数和，然后差分做差即可。

代码：

int f(int n)
{
    int cnt=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        cnt+=(n/l)*(l+r)*(r-l+1)/2;
    }
    return cnt;
}
signed main()
{
    int x=read(),y=read();
    print(f(y)-f(x-1));
    return 0;
}

P3935 Calculating

大致题意：若 x 分解质因数结果为 x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}，令f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)，求 \sum_{i=l}^rf(i) 对 998\,244\,353 取模的结果。

（忘记取模还 WA 了一发/kk）

思路：我们记一个数 i 的因数个数为 d(i)，则原题中的 f(i)=d(i)。

所以原题就变为 \displaystyle\sum^n_{i=1}\displaystyle\sum_{j|i} 不难发现和第一题相同。所以 \displaystyle\sum^n_{i=1}\displaystyle\sum_{j|i}=\displaystyle\sum^n_{i=1}\lfloor\frac{n}{i}\rfloor，依旧数论分块。

接下来证明为什么 f(i)=d(i)：

显然是排列组合。

对于第 i 个因子，我们最多可以取 k_i 个，做少可以取 0 个，所以方案数为 k_i+1。

推广到所有因子，不难发现 d(i)=\displaystyle\prod_{i=1}^n(k_i+1)，与 f(i)相同，证毕。

代码：

int query(int n)
{
    int cnt=0;
    for(int l=1,r=0;l<=n&&r<=n;l=r+1)
    {
        r=n/(n/l);
        cnt+=(n/l)*(r-l+1);
        cnt%=mod;
    }
    return cnt%mod;
}
signed main() 
{
    int l=read(),r=read();
    print((query(r)-query(l-1)+mod)%mod);
    return 0;
}

P2257 YY的GCD

题目大意：给定两个整数 n,m，求 x\in[1,n],y\in[1,m] 且 \gcd(x,y) 为质数的 (x,y) 有多少对。

前置知识：数论分块，莫比乌斯反演。

思路：

显然可以数论分块。