数论笔记 I
|
2.2k 字

摘要：杜教筛，类欧几里得

杜教筛

杜教筛被用来处理数论函数的前缀和问题。对于求解一个前缀和，杜教筛可以在低于线性时间的复杂度内求解。

引入

对于数论函数 $f$，我们要计算其前缀和，也就是：

$$S(n)=\sum_{i=1}^{n}f(i)$$

需要注意的是：

  1. 杜教筛不要求函数一定有积性

  2. 使用限制：$f(i)$，$(g*f)(i)$前缀和能快速求出

构造数论函数 $g$，则：

$$\begin{aligned}&\sum_{i=1}^{n}(g*f)(i)\\ =&\sum_{i=1}^{n}\sum_{d\mid i}g(d)f\left(\frac{i}{d}\right)\\ =&\sum_{i=1}^{n}\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor} g(i)f(j)\\ =&\sum_{i=1}^{n}g(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor} f(j)\\ =&\sum_{i=1}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ =&\sum_{i=2}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)+g(1)S(n)\\ \end{aligned}$$

所以：

$$g(1)S(n)=\sum_{i=1}^{n}(g*f)(i)-\sum_{i=2}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$

莫比乌斯函数前缀和

$$\because\epsilon=\mu\ast I\\ \therefore S(n)=1-\sum_{i=2}^{n}S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$

后半部分数论分块，预处理前 $n^{\frac{2}{3}}$ 项，时间复杂度 $O(n^{\frac{2}{3}})$。

void PreWork() {
    // 预处理 miu[1->1e7]
    // 预处理 sum[] 维护 miu[] 前缀和
}

llt SUM_miu (int x) {
    if (x < mx) return sum[x];
    if (mp.find(x) != mp.end()) return mp[x];
    llt val = 1ll;
    for (llt i = 2, j; i <= x; i = j + 1) {
        j = x / (x / i);
        val -= SUM_miu(x / i) * (j - i + 1);
    }
    return mp[x] = val;
}

实测 unordered_map 比 map 慢 0.05s，离谱。

欧拉函数前缀和

莫比乌斯反演

$$\begin{aligned}&\sum_{i=1}^{n}\sum_{j=1}^{n}1[\gcd(i,j)=1]\\ =&\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{d\mid i,d\mid j}\mu(d)\\ =&\sum_{d=1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor^2\end{aligned}$$

所以：

$$\begin{aligned}&\sum_{i=1}^{n}\sum_{j=1}^{i}1[\gcd(i,j)=1]\\ =&\frac{\sum_{d=1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor^2}{2}\\ \end{aligned}$$

类欧几里得

引入 $f$

设:

$$f(a,b,c,n)=\sum _{i=0}^{n}\left\lfloor\frac{ai+b}{c}\right\rfloor$$

先考虑 $a\ge c\ ||\ b\ge c$ 的情况:

$$\begin{aligned}f(a,b,c,n)&=\sum_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor\\ &=\sum_{i=0}^n\left\lfloor \frac{\left(\left\lfloor\frac{a}{c}\right\rfloor c+a\bmod c\right)i+\left(\left\lfloor\frac{b}{c}\right\rfloor c+b\bmod c\right)}{c}\right\rfloor\\ &=\sum_{i=0}^{n}\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor+\left\lfloor\frac{\left(a\bmod c\right)i+\left(b\bmod c\right)}{c} \right\rfloor\\ &=\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor+\sum_{i=0}^n\left\lfloor\frac{\left(a\bmod c\right)i+\left(b\bmod c\right)}{c}\right\rfloor\\ &=\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor +(n+1)\left\lfloor\frac{b}{c}\right\rfloor+f(a\bmod c,\ b\bmod c,\ c,\ n) \end{aligned}$$

在第四步进行转化时用到了一点数学知识（其中 $C$ 为常数项）:

$$\sum_{i=0}^{n}i*C=\frac{n(n+1)}{2}C$$

同理可得：

$$\sum_{i=0}^{n}i^2*C=\frac{n(n+1)(2n+1)}{6}C$$

我们会在下面用到。

然后就是 $a<c,b<c$ 的情况（设 $m=\left\lfloor\frac{an+b}{c}\right\rfloor-1$）：

$$\begin{aligned}f(a,b,c,n)&=\sum_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor\\ &=\sum_{i=0}^{n}\sum_{j=0}^{\left\lfloor\frac{ai+b}{a}-1\right\rfloor}1\\ &=\sum_{i=0}^{n}\sum_{j=0}^{m}\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\\ \end{aligned}$$

尝试更换枚举项（限制转移）：

$$\begin{aligned}j+1&\le\frac{ai+b}{c}\\ jc+c&\le ai+b\\ jc+c-b-1&<ai\\ i&>\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\end{aligned}$$

于是原式化为：

$$\begin{aligned}f(a,b,c,n)&=\sum_{j=0}^{m}\sum_{i=0}^n\left[i>\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor \right]\\ &=\sum_{j=0}^{m} (n-\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor)\\ &=n(m+1)-f\left(c,c-b-1,a,m\right) \end{aligned}$$

推导 $g$

设:

$$g(a,b,c,n)=\sum _{i=0}^{n}i\left\lfloor\frac{ai+b}{c}\right\rfloor$$

先考虑 $a\ge c\ ||\ b\ge c$ 的情况，与上文类似，我们可以得到：

$$g(a,b,c,n)=\frac{n(n+1)(2n+1)}{6}\left\lfloor\frac{a}{c}\right\rfloor+\frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor+g(a\bmod c,\ b\bmod c,\ c,\ n)$$

然后就是 $a<c,b<c$ 的情况（同样地设 $m=\left\lfloor\frac{an+b}{c}\right\rfloor-1$，$t=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor$）：

$$\begin{aligned}g(a,b,c,n)&=\sum_{i=0}^ni\left\lfloor \frac{ai+b}{c} \right\rfloor\\ &=\sum_{j=0}^{m}\sum_{i=0}^ni\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\\ &=\sum_{j=0}^{m}\sum_{i=0}^ni[i>t]\\ &=\sum_{j=0}^{m}\frac{1}{2}(t+n+1)(n-t)\\ &=\frac{1}{2}\left[(m+1)n(n+1)-\sum_{j=0}^{m-1}t^2-\sum_{j=0}^{m-1}t\right]\\ &=\frac{1}{2}[(m+1)n(n+1)-h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m)]\end{aligned}$$

推导 $h$

设:

$$h(a,b,c,n)=\sum _{i=0}^{n}\left\lfloor\frac{ai+b}{c}\right\rfloor^2$$

先考虑 $a\ge c\ ||\ b\ge c$ 的情况：

$$\begin{aligned}h(a,b,c,n)&=h(a\bmod c,b\bmod c,c,n)\\ &+2\left\lfloor\frac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n)+2\left\lfloor\frac{a}{c}\right\rfloor g(a\bmod c,b\bmod c,c,n)\\ &+\left\lfloor\frac{a}{c}\right\rfloor^2\frac{n(n+1)(2n+1)}{6}+\left\lfloor\frac{b}{c}\right\rfloor^2(n+1)+\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor n(n+1)\end{aligned}$$

然后就是 $a<c,b<c$ 的情况（同样地设 $m=\left\lfloor\frac{an+b}{c}\right\rfloor-1$，$t=\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor$）：

这里用到了一点数学技巧:

$$n^2=2\dfrac{n(n+1)}{2}-n=\left(2\sum_{i=0}^ni\right)-n$$

这样做的意义在于不会出现 $\sum\times\sum$ 的形式：

$$\begin{aligned}h(a,b,c,n)&=\sum_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor^2\\ &=\sum_{i=0}^n\left[\left(2\sum_{j=1}^{\left\lfloor \frac{ai+b}{c} \right\rfloor}j \right)-\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\\ &=\left(2\sum_{i=0}^n\sum_{j=1}^{\left\lfloor \frac{ai+b}{c} \right\rfloor}j\right) -f(a,b,c,n)\\ \end{aligned}$$

接下来考虑化简前一部分：

$$\begin{aligned}&\sum_{i=0}^n\sum_{j=1}^{\left\lfloor \frac{ai+b}{c} \right\rfloor}j\\ =&\sum_{i=0}^n\sum_{j=0}^{\left\lfloor \frac{ai+b}{c} \right\rfloor-1}(j+1)\\ =&\sum_{j=0}^{m}(j+1)\sum_{i=0}^n\left[j<\left\lfloor \frac{ai+b}{c} \right\rfloor\right]\\ =&\sum_{j=0}^{m}(j+1)\sum_{i=0}^n[i>t]\\ =&\sum_{j=0}^{m}(j+1)(n-t)\\ =&\frac{1}{2}n(m+1)(m+2)-\sum_{j=0}^{m}(j+1)\left\lfloor \frac{jc+c-b-1}{a} \right\rfloor\\ =&\frac{1}{2}n(m+1)(m+2)-g(c,c-b-1,a,m)-f(c,c-b-1,a,m)\end{aligned}$$

最终得到：

$$h(a,b,c,n)=n(m+1)(m+2)-2g(c,c-b-1,a,m)-2f(c,c-b-1,a,m)-f(a,b,c,n)$$

板子题

luogu_P5170

此题卡 $\bmod$ 非常严重，建议有事没事按俩 % p 。

#include<bits/stdc++.h>
using namespace std;
typedef long long llt;
const llt p = 998244353;
const llt inv2 = 499122177;
const llt inv6 = 166374059;

struct zerc {
    llt f, g, h;
    void mod() {
        f = (f % p + p) % p, 
        g = (g % p + p) % p, 
        h = (h % p + p) % p;
    }
};

zerc calc(llt n, llt a, llt b, llt c) {	
    // printf("|> %lld %lld %lld %lld\n", n, a, b, c);
    llt m = ((a * n + b) / c - 1);
    llt n1bc = ((n + 1) * (b / c)) % p;
    llt n1bc2= ((n + 1) * (b / c) % p * (b / c) % p) % p;
    llt n2ac = (n * (n + 1) % p * inv2 % p * (a / c) % p) % p;
    llt n2bc = (n * (n + 1) % p * inv2 % p * (b / c) % p) % p;
    llt n21acbc = (n * (n + 1) % p * (a / c) % p * (b / c) % p) % p;
    llt n3ac = (n * (n + 1) % p * (n * 2 + 1) % p * inv6 % p * (a / c) % p)  % p;
    llt n3ac2= (n * (n + 1) % p * (n * 2 + 1) % p * inv6 % p * (a / c) % p * (a / c) % p)  % p;
    zerc d, e;
    if (!a) {
        d.f = n1bc;
        d.g = n2bc;
        d.h = n1bc2;
        return d;
    }
    if (a >= c || b >= c) {
        d.f = n2ac + n1bc;
        d.g = n3ac + n2bc;
        d.h = n3ac2 + n1bc2 + n21acbc;
        d.mod();
        e = calc(n, a % c, b % c, c);
        d.f += e.f;
        d.g += e.g;
        d.h += e.h + (b / c) * 2 * e.f % p + (a / c) * 2 * e.g % p;
        d.mod();
        return d;
    }
    if (a < c && b < c) {
        e = calc(m, c, c - b - 1, a);
        d.f = (n * (m + 1) % p - e.f) % p;
        d.mod();
        d.g = (n * (m + 1) % p * (n + 1) % p - e.h - e.f) % p * inv2 % p;
        d.mod();
        d.h = (n * (m + 1) % p * (m + 2) % p - e.g * 2 % p - e.f * 2 % p - d.f) % p;
        d.mod();
        return d;
    }
    return d;
}

int main() {
    freopen("P5170_6.in", "r", stdin);
    freopen("P5170.out", "w", stdout);
    int T; scanf("%d", &T); while (T--) {
        llt n, a, b, c;
        scanf("%lld %lld %lld %lld", &n, &a, &b, &c);
        zerc ans = calc(n, a, b, c);
        printf("%lld %lld %lld\n", ans.f, ans.h, ans.g);
    }
    return 0;
}
上一篇
下一篇