数论好难怎么办

数论很差，所以开个板块写数论。

其实偏向技巧吧。

下文中 $p$ 默认为质数，$P$ 为质数集。

基础知识

Fermat 小定理

当 $a\perp p$ 时，$a^{p-1}\equiv 1\pmod p$。

下面来证明。

首先有一个引理：当 $a$ 不是 $p$ 的倍数时，$\forall x\not =y,1\le x,y<p$ 有 $xa\not\equiv ya\pmod p$。移项后易证。

于是

$$\prod\limits_{i=1}^{p-1} i\equiv\prod\limits_{i=1}^{p-1}ai\equiv a^{p-1}\prod\limits_{i=1}^{p-1}i\pmod p\iff a^{p-1}\equiv 1\pmod p$$

乘法逆元

满足 $ax\equiv 1\pmod b$ 的 $x$ 为 $a$ 在模 $b$ 意义下的乘法逆元。

逆元不一定唯一，不一定存在，当且仅当 $a\perp p$ 时存在逆元。在模 $p$ 下的乘法逆元记作 $(a^{-1})_p$，简记为 $a^{-1}$。

对于质数，可以直接用 Fermat 小定理求：$a^{-1}\equiv a^{-1}\cdot 1\equiv a^{p-2}\pmod p$。

Lagrange 定理

简单来说，$n$ 次多项式在模 $p$ 意义下，至多有 $n$ 个不同解。

Wilson 定理

首先，逆元是相互的。即 $ax\equiv 1\pmod p$，说明 $a$ 与 $x$ 互为逆元。

考虑 $1\sim p-1$ 的数两两配对，由于 $x^2\equiv 1\pmod p$ 仅有解 $x\equiv\pm 1$，因此 $2\sim p-2$ 中的数两两配对，有 $(p-1)!\equiv\prod\limits_{i=1}^{p-1} i\equiv-1\pmod p$，当且仅当 $p$ 为质数。

扩展形式

设 $1\sim p^k$ 中所有与 $p$ 互质数的成绩模 $p^k$ 为 $(p^k!)_p$。

类似的，有 $(p^k!)^p=\begin{cases}1,&p=2\land k\ge3\-1&\text{otherwise}\end{cases}$ 。

Kummer 定理

设 $\nu_p(n)=k$ 表示 $k$ 为最大的使 $p^k\mid n$ 的数，$s_p(n)$ 表示 $p$ 进制下 $n$ 的数位和。

则 $\nu_p\left(\dbinom nm\right)$ 为 $p$ 进制下，$n$ 减去 $m$ 需要借位的次数，即 $n+m$ 进位的次数，为 $\dfrac{s_p(m)+s_p(n-m)-s_p(n)}{p-1}$。

下面来证明这个定理，设 $d=\lfloor\log_p n\rfloor$，$n=\sum\limits_{i=0}^da_ip^i$

$$\begin{aligned}\nu_p(n!)&=\sum\limits_{i=0}^{d}a_i\sum \limits_{j=1}^i p^{j-1}\&=\sum\limits_{i=0}^d a_i\dfrac{p^i-1}{p-1}\&=\dfrac{n-s_p(n){}}{p-1}\end{aligned}$$

代入到组合数中即可。

步长与子环

在长为 $n$ 的环上，步长为 $k$。有 $d=\gcd(n,k)$ 个子环，每个子环的环长为 $\dfrac nd$。

这是比较显然的，每次走一步相当于在模 $n$ 意义下加了 $\dfrac kd$ 个 $d$。考虑回到起点走了多少步，即使 $p\cdot\dfrac kdd\equiv 0\pmod n$ 满足的最小 $p$，由于 $\dfrac kd\perp n$，因此 $p=\dfrac nd$ 时为最小。

故子环环长为 $\dfrac nd$。而对于子环数，直接用除一下就好了。

而当 $k\perp n$ 时，那么 $ck\bmod n$ 覆盖了所有点。

Euler 定理

$a^{\varphi(p)}\equiv 1\pmod p$

exEuler 定理

$$a^b\equiv\begin{cases}a^{b\bmod \varphi(p)},&\gcd(a,p)=1\a^b,&\gcd(a,p)\not=1\and b<\varphi(p)\a^{b\bmod \varphi(p)+\varphi(p)},&\gcd(a,p)\not= 1\land b\ge\varphi(p)\end{cases}\pmod p$$

P6187 [NOI Online #1 提高组] 最小环

给出长度为 $n$ 的序列，构成一个圆环。定义距离 $d$ 的贡献，为任意距离为 $d$ 的两个数乘积之和。

$m$ 次询问，给出 $d$，求距离 $d$ 的贡献。

$1\le m\le n\le 2\times 10^5$。

根据上面的理论，实际上距离 $d$ 的贡献等价于最大化将 $n$ 划分成 $\dfrac n{\gcd(n,d)}$ 组后最大乘积的和。$n$ 的因子是 $\mathcal O(\sqrt n)$ 的，故本质不同的询问只有 $\mathcal O(\sqrt n)$ 种。

考虑如何最大化划分，即将 $n$ 个数均等划分到 $d$ 个圆环上，求各个圆环相邻数乘积之和的和的最大值。

先看一个圆环怎么做，考虑从小到大插入。每次插入一定在次大与最大值之间，这样保证步步最优。假设 $a_i$ 为排序后的序列，$\prod\limits_{i=1}^n a_{\sigma(i)}a_{\sigma((i+1)\bmod n)}$ 最大即为 $\prod\limits_{i=1}^{i-2} a_ia_{(i+2)}+a_1a_2+a_{n-1}a_n$。

拓展到多个圆环，那么直接排序一遍然后分组，根据上面的贪心，直接按照大小每环长个为一组即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

int main (void) {

    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf ("%lld", a + i), f[0] += a[i] * 1ll * a[i];
    sort (a + 1, a + n + 1);
    for (int i = 1; i <= n >> 1; i ++) {
        if (n % i) continue;
        int l = n / i;
        vector <ll> sub;
        for (int j = 1; j <= n; j ++) { 
            sub.push_back (a[j]);
            if (j % l == 0)  {
                f[i] += sub.back () * 1ll * sub[sub.size () - 2];
                while (sub.size () >= 3) {
                    f[i] += sub.back () * 1ll * sub[sub.size () - 3];
                    sub.pop_back ();
                }
                f[i] += sub[0] * 1ll * sub[1];
                sub.clear ();
            }
        } 
    }

    while (m --) {
        int d; scanf ("%d", &d);
        if (!d) printf ("%lld\n", f[0]);
        else printf ("%lld\n", f[__gcd (n, d)]);
    }

    return 0;
}

二元线性不定方程

Bézout 定理

$ax+by=c$ 有解当且仅当 $\gcd (a,b)\mid c$。

充分性是显然的，因为左式为 $\gcd (a,b)$ 的倍数。

对于必要性，对左右二式同时除以 $\gcd(a,b)$，为 $a’x+b’y=c’$。问题转化为 $a’x\equiv c\pmod {b’}$。由于 $a’\perp b’$，根据前文，$a’$ 的若干倍覆盖 $0\sim b’-1$，因此成立。

扩展 Euclid 算法 - exgcd

先看看普通的 Euclid 算法：$\gcd(a,b)=\gcd(b,a\bmod b)$。

用到不定方程上，设 $d=\gcd(a,b)$，$ax+by=pd$ 其实就是求 $ax+by=d$。

$$\begin{aligned}ax+by&=bx’+(a-\left\lfloor\dfrac{a}{b}\right\rfloor\cdot b)y’\&=ay’+b(x’-\left\lfloor\dfrac{a}{b}\right\rfloor y’)\end{aligned}$$

直接递归求解即可。

1
2
3
4
5

void exgcd (int a, int b, int& x, int& y) {
	if (!b) return x = 1, y = 0, void ();
    exgcd (b, a % b, y, x);
    y -= a / b * x;
}

P2261 [CQOI2007] 余数求和

$$\begin{aligned}G(n,k)&=\sum\limits_{i=1}^nk\bmod i\&=\sum\limits_{i=1}^n(k-\lfloor\dfrac ki \rfloor \cdot i)\&=\sum\limits_{i=1}^nk-\sum\limits_{i=1}^n i\cdot\lfloor\dfrac ki\rfloor\end{aligned}$$

接下来数论分块即可。复杂度为 $\mathcal O(\sqrt n)$。

1
2
3
4
5
6
7

ll ans = 0;
ans = n * k;
for (ll l = 1, r; l <= n; l = r + 1) {
    if (k / l == 0) break ;
    r = k / (k / l);
    ans -= sum (l, min (r, n)) * (k / l);
}

P2155 [SDOI2008] 沙拉公主的困惑

根据欧几里得算法，有 $\gcd(x,y)=\gcd(x+y,y)$。即若 $\gcd(x,m!)=1$，那么有 $\gcd (x+m!,m!)=1$。那么 $[1,m!]$ 中所有与 $[m!+1,2\times (m!)]$ 以及任何一个周期区间内，互质数的个数是一一对应的。

进而得到答案是 $\dfrac{n!}{m!}\varphi (m!)$。

考虑如何预处理 $\varphi(m!)$。

观察展开形式：$\varphi(m!)=m!\prod(1-\dfrac 1{p_i})$，其中 $p_i$ 是 $m!$ 的质因数。而 $m!=m\times (m-1)!$，当 $m$ 为质数时，$\varphi(m!)\gets\varphi((m-1)!)\times m\times (1-\dfrac{1}{m})$；反之，$\varphi(m!)\gets \varphi((m-1)!)\times m$。这是由于 $[1,m)$ 中所有数都是 $(m-1)!$ 的因子，$m$ 不是质数则其质因子必然被其全部包含。

此外，在处理阶乘时，可能会出现有因子 $R$ 的情况。只要在 $(m,n]$ 间出现 $R$ 的倍数，答案为 $0$。若无，那么只需在预处理阶乘时遇倍数则跳过即可。

素性检测及质因子分解

Miller-Rabin 素性检测

实际上是基于概率的检测方式。

Fermat 素性检测

Fermat 小定理告诉我们对于质数，任意正整数 $a<p$，都有 $a^{p-1}\equiv 1\pmod p$。

对于满足这个条件但不是质数的数，称为 Carmichael 数。

二次探测定理

根据 Lagrange 定理，若 $p$ 为奇质数，则 $x\equiv 1\pmod p$ 仅有两个解 $x\equiv \pm 1\pmod p$。

然而这是充分条件，例如模 $4$ 意义下，仍然只有 $\pm1$ 两个解。

进一步的 Miller-Rabin

设 $n-1=2^sd$。若 $n$ 为质数，那么对于任意正整数 $a<n$ 都有 $a^{n-1}\equiv 1\pmod n$。

考虑随机 $a$，多次运用二次探测定理，若 $n$ 为质数，必然下式其一成立。

• $a^d\equiv 1$ 或者 $a^{2^rd}\equiv -1\text{ for }0\le r< s$。

也就是求出 $a^d$ 之后，不断对其进行平方操作。直至有一个平凡解时，才成立。

可以证明，对于值域在 $[1,2^{64}]$ 范围内的质数，只要选取前 $12$ 个质数作为 $a$ 进行检测即可。或者选取 ${2,325,9375,28178,450775,9780504,1795265022}$ 七个数进行素性检测。

Pollard-Rho

生日悖论

$n$ 个数的集合中，抽到相同数的期望为 $\mathcal O(\sqrt n)$。

朴素试除

枚举 $1\sim \sqrt n$ 的所有数试除，复杂度 $\mathcal O(\sqrt n)$。

有一个搞笑的做法，就是随机所有数。这样的期望下最坏复杂度达到了 $\mathcal O(n)$。

不妨对数求 $\gcd$，在 $n=p^2$ 的最劣情况下，有 $\mathcal O(\sqrt n\log n)$ 的最劣期望复杂度。

伪随机序列

$f(x)=x^2+c\pmod p$ 是一个伪随机序列。

当迭代的足够多时，会成为一个循环的序列。形似 $\rho$，故得名 Rho。

为了防止随机过程中重复，采用 Floyd 判环算法。设变量 $a,b$，每次判断是否有 $\gcd(\vert a-b\vert,n)>1$，如果没有。就令 $a=f(a),b=f(f(b))$。直到 $a$ 与 $b$ 在环上相遇，重新取 $c$ 继续随机。

这样，如果 $\vert i-j\vert\equiv 0\pmod p$ 一定有 $\vert f(i)-f(j)\vert\equiv \vert i^2-j^2\vert \equiv 0\pmod p$。

期望复杂度为 $\mathcal O(n^{0.25}\log n)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

bool miller_rabin (ll x) {
    if (x < 2) return false;
    if (!(x & 1)) return x == 2;
    if (x <= 37) {
        for (const auto& pr : p) if (pr == x) return true;
        return false;
    }
    ll s = 0, u = x - 1;
    while (!(u & 1)) u >>= 1, s ++;
    for (const auto& a : p) {
        i128 tmp = qpow (a, u, x);
        if (tmp == 1) continue;
        int r = 0; for (; r < s; r ++) {
            if (tmp == x - 1) break ;
            tmp = tmp * tmp % x;
        }
        if (r == s) return false; 
    }
    return true;
}

ll pollard_rho (ll n) {
    if (miller_rabin (n)) return n;
    if (n == 4) return 2;

    while (true) {
        ll c = rnd () % (n - 1) + 1;
        auto f = [&](ll x) {
            return ((i128)x * x + c) % n;
        };
        ll a = f (0), b = f (f (0));
        while (a != b) {
            ll d = __gcd (abs (a - b), n);
            if (d > 1) return d;
            a = f (a), b = f (f (b));
        }
    }
}

CRT & exCRT

$$\begin{cases}x\equiv a_1\pmod {m_1}\x\equiv a_2\pmod {m_2}\\cdots\x\equiv a_n\pmod{m_n} \end{cases}$$

满足 $m$ 两两互质，求 $x$ 的最小解。

• 构造即可，设 $M=\prod m$，$M_i=\dfrac{\prod m}{m_i}$。则 $x=\sum\limits a_iM_im_i^{-1}$，这和 Lagrange 插值法的思想是一致的。

当 $m$ 不两两互质呢？

返璞归真。先看两个方程，我们可以合并：$x=m_1x_1+a_1=m_2x_2+a_2$，即 $m_1x_1-m_2x_2=a_2-a_1$，exgcd 求解即可。更多的，不断递归下去即可。

• 实际上，CRT 更为直接的应用为合并模数非质数的结果，如 P2480 [SDOI2010] 古代猪文 一题中就是这种做法。以及下面的一道例题。

Lucas & exLucas

当 $P$ 为质数 $p$ 时，${n\choose m}\equiv {{\lfloor\frac nP\rfloor}\choose{\lfloor\frac mP\rfloor}}{{n\bmod P}\choose{m\bmod P}}\pmod P$。

为啥？

Lemma 1. $(1+x)^p\equiv 1+x^p \pmod p$

• 二项式定理展开

那么 $$\begin{aligned}(1+x)^n&=(1+x)^{\lfloor\frac np\rfloor p}(1+x)^{n\bmod p}\&=(1+x^p)^{\lfloor\frac np\rfloor}(1+x)^{n\bmod p}\end{aligned}$$

根据二项式定理，得证。

当 $P$ 非质数时。

首先考虑 $P=p^k$ 的答案。

Lemma 2. Kummer 定理：设 $\nu_p(x)$ 表示最大的 $k$ 使得 $p^k\mid x$。有 $\nu_p(n!)=\sum\limits_{i=1}^{\lfloor\log_pn\rfloor}\lfloor\dfrac{ n}{p^i}\rfloor$。

于是下面的式子就能算了：

$$\begin{aligned}{n\choose m}&=\dfrac {n!}{m!(n-m)!}\&=\dfrac{n!/p^{\nu_p(n!)}}{m!(n-m)!/p^{\nu_p(m!)+\nu_p((n-m)!)}}\times p^{\nu_p(n!)-{\nu_p(m!)-\nu_p((n-m)!)}}\end{aligned}$$

Lemma 3. Wilson 定理及拓展：$(p-1)!\equiv -1\pmod p\iff p \text{ is a prime.}$

$$

例题

例题 P3726 [AHOI2017/HNOI2017] 抛硬币

若 $a=b$，胜与负的情况是一一对应ds

离散对数

使得 $g^x\equiv b\pmod p$ 的 $x$ 为 $b$ 的离散对数。

BSGS

若 $\gcd(g,p)=1$： 考虑分块，设块大小为 $B=\sqrt P$，设 $x=aB-c$，原式即为 $g^{aB}\equiv b\cdot g^c\pmod p$，用哈希查询即可。

exBSGS

若 $\gcd(g,p)\not=1$： 令 $d=\gcd(g,p)$，那么必然有 $d\mid b$，否则无解。 那么可以同除 $d$：$g^{x-1}\dfrac gd\equiv \dfrac bd\pmod{\dfrac pd}$。

此时 $\dfrac gd\perp\dfrac pd$，但是 $g$ 与 $\dfrac pd$ 并不一定互质，因此我们需要递归地做这一操作，直至 $g\perp \dfrac p{\prod d_i}$ 为止。

$$g^{x-t}\dfrac{g^t}{\prod d_i}\equiv\dfrac{b}{\prod d_i}\pmod {\dfrac p{d_i}}$$

此时互质，存在逆元。BSGS 即可。

阶与原根

阶

使得 $a^x\equiv 1\pmod m$ 成立的最小的 $x$ 为 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$。

$\delta_m(a)$ 存在当且仅当 $a\perp m$。

性质

1. $a^x\equiv 1\pmod m\iff \delta_m(a)\mid x$。
   • 实际上阶就是在模 $m$ 下构成的环的大小。
2. $\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(k,\delta_m(a))}=\dfrac{\operatorname{lcm}(\delta_m(a),k)}{k}$
   • 显然吧，就是 $\gcd$ 与 $\operatorname{lcm}$ 的转换。
3. $\delta_m(ab)=\delta_m(a)\delta_m(b)\iff \delta_m(a)\perp\delta_m(b)$
4. $\dfrac{\operatorname{lcm}(\delta_m(a),\delta_m(b))}{\gcd(\delta_m(a),\delta_m(b))}\mid\delta_m(ab)\mid\operatorname{lcm}(\delta_m(a),\delta_m(b))$
   • 实际上是性质 3 的推广。
5. 给定 $a,b\perp m$，一定存在 $c$ 使得 $\delta_m(c)=\operatorname{lcm}(\delta_m(a),\delta_m(b))$。

求阶

• BSGS 求 $a^x\equiv 1\pmod m$ 的最小 $x$。
• 对于 $a$ 模 $m$ 的阶，直接枚举 $\varphi(m)$ 的所有质因子 $p$。设 $x=\varphi(m)$，从小到大枚举质因子 $p$，一直除直至 $x\perp p$ 或者 $a^{x/p}\not\equiv 1\pmod m$。设质因子个数为 $\omega(\varphi(m))$，复杂度就是 $\mathcal O(m^{0.25}+q\omega(\varphi(m))\log m)$。其中 $q$ 是询问次数，$m^{0.25}$ 是 Pollard-Rho 分解质因数的复杂度。

1
2
3
4
5
6
7

auto ord = [&](ll a) {
    ll x = phi (m);
    for (const auto& pr : fact) 
        while (x % pr == 0 && qpow (a, x / pr, m) == 1) x /= pr;       
    return x;
};
// 求 a 模 m 的阶

原根

定义

若 $\delta_m(g)=\varphi(m)$，则 $g$ 为 $m$ 的原根。

实际上，原根可以生成模 $m$ 的缩系。原根就是循环群的生成元。

原根存在定理

$m$ 有原根当且仅当 $m=2,4,p^{\alpha},2p^{\alpha}$，其中 $p$ 为奇质数。

原根判定定理

根据原根定义，枚举其阶的所有质因子即可。

设 $\mathbb P$ 为 $\varphi(m)$ 的质因子集合，$g$ 为原根当且仅当 $\forall p\in\mathbb P,g^{\frac{\varphi(m)}p}\not\equiv 1\pmod m$。

原根个数

前文已经提到，原根是模 $m$ 缩系的生成。故缩系中的所有元素都可以用 $g^k\bmod m$ 表示。其阶等于 $\delta_m(g^k)=\dfrac{\varphi (m)}{\gcd(\varphi(m),k)}$。于是原根的个数就是与 $\varphi(m)$ 互质的 $k$ 的个数，即 $\varphi(\varphi(m))$。

求原根

王元和 Burgess 证明了素数的最小原根量级为 $\mathcal O(p^{0.25+\epsilon})$。

因此可以枚举 + 原根判定定理求原根，复杂度为 $\mathcal O(p^{0.25}\omega(\varphi(p)))\log p$。

例题

P5605 小 A 与两位神仙

给出 $m=p^{\alpha}$，多次询问，给出 $x,y\perp m$，询问是否存在 $a$ 使得 $x^a\equiv y\pmod m$。

其中 $p$ 为奇质数，$m\le 10^{18}$，$1\le x,y<m$。

$m$ 存在原根。设为 $g$，设 $x\equiv g^X,y\equiv g^Y\pmod m$。问题等价于 $aX\equiv Y\pmod {\varphi(m)}$ 的存在性问题。由 Bezout 定理，得 $\gcd(X,\varphi (m))\mid Y$ 时有解。这个东西等价于 $\gcd(X,\varphi(m))\mid\gcd(Y,\varphi (m))$。

由于 $\delta_m(x)=\dfrac{\delta_m(g)}{\gcd(\delta_m(g),X)}\implies \gcd(\varphi(m),X)=\dfrac{\varphi(m)}{\delta_m(x)}$。条件等价于 $\delta_m(y)\mid\delta_m(x)$。

直接求阶。对于 $\varphi(m)$，可以直接 Pollard-Rho。

复杂度 $\mathcal O(q\log^2 V+V^{0.25})$。

结论

对于奇质数幂 $p^\alpha$ 和 $x,y\perp p$，$x^\alpha\equiv y\pmod {p^\alpha}$ 有解当且仅当 $\delta_{p^{\alpha}}(y)\mid\delta_{p^\alpha}(x)$。

P6730 [WC2020] 猜数游戏

给出 $n$ 个小于 $p$ 的数 $a_i$。当存在 $k$ 使得 $a_i^k\equiv a_j\pmod p$ 成立时，称 $a_j$ 是可被 $a_i$ 表示的。对 $a_i$ 染色，就会染色所有可被其表示的数。

对于 $a_i$ 的所有非空子集，求出最小染色次数，使得集合内所有数都被染色。求次数之和。

$n\le 5000,p\le10^8$，保证 $p$ 为素数的正整数次幂。

对于与 $p$ 互质的 $x,y$，这个条件相当于 $\delta_p(y)\mid \delta_p(x)$。

对于不互质的 $x,y$，由于 $p$ 为素数的正整数次幂，故不超过 $\log$ 次就会变成 $0$。这一部分直接暴力即可。

这样我们就能建出图，一条有向边表示 $u$ 可以表示 $v$。进一步的，若 $u$ 能表示 $v$，那么 $u$ 可以表示 $v$ 所表示的所有数。现在考虑如何统计。

考虑每个数对答案的贡献。具体的，一个数对答案有贡献，当且仅当其所在集合 $S$ 不存在能生成 $a$ 的数。拓展到所有集合，就是不存在能表示出它的数的集合数，设能表示出它的数的个数为 $c$，那么它对答案的贡献就是 $2^{n-c}$。对于一个 DAG，这种做法是十分正确的。但是对于存在环的图，直接统计环上点只会统计到该环只有该点。考虑缩点，对于缩点后的点，做出贡献必须在其中任意一点都有贡献，故缩点后贡献为 $(2^{\vert \mathrm{SCC}\vert}-1)2^{n-\vert \mathrm{SCC}\vert-c’}$，$c’$ 为可以到达它的点的大小之和。

数论函数

积性函数

积性函数：若 $f(x)$ 对于 $\gcd(x,y)=1$ 都有 $f(xy)=f(x)f(y)$，那么 $f(x)$ 为 积性函数。 完全积性函数：若 $f(x)$ 对于 $\forall x,y\in \mathrm{Z}$ 都有 $f(xy)=f(x)f(y)$，那么 $f(x)$ 为 完全积性函数。

常见数论函数

$\begin{aligned}\operatorname{id}k(n)&=n^k\1(n)&=1\ \sigma_k(n)&=\sum\limits{d\mid n}d^k\ \epsilon(n)&=[n=1]\ \varphi(n)&=\sum\limits_{i=1}^n[\gcd(i,n)=1]\\end{aligned}$

莫比乌斯函数

定义莫比乌斯函数：$\mu(n)=\begin{cases}1,&n=1\(-1)^k,&n=\prod\limits_{i=1}^k p_i\0,&\textrm{otherwise}\end{cases}$。

狄利克雷卷积与常见反演

两个数论函数 $f(x)$，$g(x)$，两者的狄利克雷卷积 $h(x)=(f*g)(x)=\sum\limits_{d\mid x}f(d)\cdot g(\frac nd)$。

如下，有两个重要结论： $\begin{aligned}\operatorname{id}&=\varphi1\\epsilon&=\mu1\end{aligned}$

以及反演：

$$f(x)=\sum\limits_{d\mid x}g(d)\iff g(x)=\sum\limits_{d\mid x}\mu(d)\cdot f(\dfrac nd)$$

Dirichlet 前缀和

https://www.luogu.com.cn/problem/P5495

对于 $b_i=\sum\limits_{d\mid i}a_d$，求 $b_1,b_2,\cdots,b_n$。

$n\le 2\times 10^7$。

一个简单的想法，就是枚举所有数并计算对于其他数的贡献，这个做法是 $\mathcal O(n\log n)$ 的，无法通过，考虑优化。

设 $a$ 的因子组成的集合为 $S(a)$，那么当 $d\mid a$ 时，自然有 $S(d)\subseteq S(a)$。

由于所求为 $b_i=\sum\limits_{d\mid i} a_d$，故只需要注意所有 $d\in S(i)$ 满足 $\forall d’\in S(i)$ 且 $d’\not = d$ 的 $d$，对 $b_d$ 求和即可。

对于第二个性质，实际上等价于 $i$ 为一个质数与 $d$ 之积。这与埃式筛的做法不谋而合，复杂度同埃式筛，为 $\mathcal O(n\log\log n)$。

下面换一个角度来考虑这个问题。

设 $i=\prod p_k^{\alpha_k}$，$j=\prod p_k^{\beta_k}$。若 $a_i$ 对 $b_j$ 有贡献，那么必然对于任意 $k$，都有 $\alpha_k\le \beta_k$。这完全可以转化成以每个质因子为维度的高维前缀和问题，每个维度差之和为 $1$。于是考虑枚举每个质数以及每个数，统计即可。

1
2
3
4

for (int i = 1; i <= n; i ++) {
    if (!vis[i]) for (int j = 1; j * i <= n; j ++) a[i * j] += a[j], vis[i * j] = true;
    ans ^= a[i];
}

P3327 [SDOI2015] 约数个数和

一个 Trick：$d(xy)=\sigma_0(xy)=\sum\limits_{i\mid x}^n\sum\limits_{j\mid y}^m[\gcd(i,j)=1]$ 考虑证明：$d(n)=\prod$

几个筛法

杜教筛

求积性函数的前缀和 $S(n)=\sum\limits_{i=1}^n f(i)$，可以构造另外两个积性函数 $h=f*g$： $\begin{aligned}\sum\limits_{i=1}^n h(i) &=\sum\limits_{i=1}^n\sum\limits_{d\mid i}g(d)f(\frac nd)\ &=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}f(i)\g(1)S(n)&=\sum\limits_{i=1}^nh(i)-\sum\limits_{d=2}^ng(d)S(\lfloor \frac nd \rfloor)\end{aligned}$

尝试构造合适的 $g(d)$，使用 整数分块 快速求解。

例 【模板】杜教筛

求 $\sum\limits_{i=1}^n\varphi(i)$ 以及 $\sum\limits_{i=1}^n\mu(i)$，$n<2^{31}$。

由 $\operatorname{id}=\varphi1$，则 $S(n)=\sum\limits_{i=1}^n i-\sum\limits_{d=2}^n S(\lfloor\dfrac nd\rfloor)$。由 $\epsilon=\mu1$，有 $S(n)=1-\sum\limits_{d=2}^n S(\lfloor\dfrac{n}{d}\rfloor)$。整数分块即可。

code

min_25 筛

一个好博客

Powerful Number 筛