数论

数论

数论基础

整除

整除的定义 : 设 $a, b \in \mathbb{Z}, a \not = 0$ ，如果 $\exists q \in \mathbb{Z}$ ，使得 $b = aq$， 那么就可以说 $b$ 可被 $a$ 整除， 记作 $a | b$ ，$b$ 不被 $a$ 整除记作 $a \not | b$。

约数 : 若 $a | b$ ， 则称 $b$ 是 $a$ 的倍数， $a$ 是 $b$ 的约数。

素数与合数

设整数 $p \ne 0,\pm 1$。如果 $p$ 除了平凡约数外没有其他约数，那么称 $p$ 为素数（不可约数）。

若整数 $a \ne 0,\pm 1$ 且 $a$ 不是素数，则称 $a$ 为合数。

所有大于 $3$ 的素数都可以表示为 $6n \pm 1$ 的形式。

算术基本定理

设正整数 $a$ ， 那么必有表示 :

$$a = p_1 ^ {k_1} p_2 ^ {k_2} \cdots p_s ^ {k_s}, p_1 < p_2 < \cdots < p_s$$

其中 $p_i (1 \le i \le s)$ 为素数。

同余

同余的定义 : 设整数 $m \not = 0$ 。 若 $m | (a - b)$， 称 $m$ 为模数， $a$ 同余于 $b$ 模 $m$， $b$ 是 $a$ 对模 $m$ 的剩余。 记作 $a \equiv b \pmod m$ 。

同余有自反性， 对称性， 传递性的性质， 可以进行线性运算，

数论函数

数论函数指定义域为正整数的函数。数论函数也可以视作一个数列。

积性函数

若函数 $f(n)$ 满足 $f(1) = 1$ 且 $\forall x, y \in \mathbb{N} ^ {*}, \gcd (x, y) = 1$ 都有 $f(x)(y) = f(x)f(y)$ ， 则 $f(n)$ 为积性函数。

若函数 $f(n)$ 满足 $f(1) = 1$ 且 $\forall x, y \in \mathbb{N} ^ {*}$ 都有 $f(x)(y) = f(x)f(y)$ ， 则 $f(n)$ 为完全积性函数。

若 $f(x)$ 和 $g(x)$ 均为积性函数， 则以下函数也为积性函数 :

$$h(x) = f(x ^ p) \\ h(x) = f ^ p (x) \\ h(x) = f(x) g(x) \\ h(x) = \sum_{d | x} f(d) g(\frac{x}{d})$$

比较常见的积性函数 :

$$d(x)= \sum_{i | n} 1 \\ \sigma (x) = \sum_{i | n} i \\ \varphi (x) = \sum_{i=1}^x 1 [gcd(x,i)=1] \\ \mu (x) = \left\{ \begin{aligned} &1 &x=1 \\ &(-1)^k &\prod_{i=1}^k q_i=1 \\ &0&\max\left\{ q_i \right\} > 1 \end{aligned} \right. \\ \epsilon (x) = [x = 1]$$

素数

素数计数函数， 将 $\pi (x)$ 记为 小于或等于 $x$ 的素数的个数， 随着 $x$ 的增大，有 $\pi (x) \sim \frac{x}{\ln x}$。

费马小定理

定义 : 若 $p$ 为 素数 ，$\gcd(a, p) = 1$ ， 则 $a ^ {p - 1} \equiv 1 \pmod p$。

证明 : 设一个质数 $p$， 然后取一个与 $p$ 互质的数 $a$ 。

首先构造一个序列 $A = {1, 2, 3, \cdots, p - 1}$， 有 :

$$\prod_{i = 1} ^ {p - 1} A_i \equiv \prod_{i = 1} ^ {p - 1} (A_i \times a) \pmod p$$

首先，

$$\because \gcd(A_i, p) = 1, \gcd(A_i \times a, p) = 1$$

可以得到每一个 $A_i \times a$ 对应一个 $A_i$， 所以该性质成立。

所以进一步可得 :

$$\prod_{i = 1} ^ {p - 1} A_i \equiv a ^ {p - 1} \times \prod_{i = 1} ^ {p - 1} A_i$$

即 :

$$a ^ {p - 1} \equiv 1 \pmod p$$

Miller Rabin

Miller Rabin 是进阶的概率性素性测试， 主要是 Fermat 的优化。

朴素的 Fermat 只使用了费马小定理来检验 :

bool fermat(int n)
{
    if(n < 3)return n == 2;
    for(int i = 1; i <= T; i++)
    {
        int a = rand() % (n - 2) + 2;
        if(qpow(a, n - 1, n) != 1)
            return 0;
    }
    return 1;
}

但是仍有满足费马小定理的合数， 也就是伪素数，这样会被特定的数据卡掉。

费马小定理的逆定理是不成立的。

上述的费马伪素数，也称为卡迈克尔数， 即对于合数 $n$ ，如果对于所有正整数 $a$ ， $a$ 和 $n$ 互质， 都有同余式 $a ^ {n - 1} \equiv 1 \pmod n$ 成立，则合数 $n$ 为卡迈克尔数。

并且， 若 $n$ 为卡迈克尔数， 则 $m = 2 ^ n - 1$ 也是一个卡迈克尔数。

Miller Rabin 则使用了更多确定性算法， 来进行素性测试，比如二次探测定理。

二次探测定理 : 对于奇素数 $p$ ， 若 $x ^ 2 \equiv 1 \pmod p$ ， 则小于 $p$ 的解只有两个， $x_1 = 1, x_2 = p - 1$。

将式子移项即可得证。

然后我们将其用在素性测试中，对于 $a ^ {n - 1}$ ，可以拆分为 $n - 1 = u \times 2 ^ t$， 先求出 $a ^ u$ ，然后依次做 $t$ 次平方， 同时检验，当前值是否满足二次探测定理，如果出现不是 $1$ 或 $n - 1$ 的解， 说明没有通过素性测试。

最后 Miller Rabin 如下

bool miller_rabin(ll p)
{
    if(p < 2)return 0;
    if(p == 2 || p == 3)return 1;
    ll d = p - 1, r = 0;
    while(!(d & 1))r++, d >>= 1;
    for(int k = 1; k <= 10; k++)
    {
        ll a = rand() % (p - 2) + 2;
        ll x = qpow(a, d, p);
        if(x == 1 || x == p - 1)continue;
        for(int i = 1; i <= r; i++)
        {
            x = (i128)x * x % p;
            if(x == p - 1)break;
        }
        if(x != p - 1)return 0;
    }
    return 1;
}

最大公约数

一组整数的公约数，是指同时是这组数中每一个数的约数的数。$\pm 1$ 是任意一组整数的公约数。

一组整数的最大公约数，是指所有公约数里面最大的一个。

欧几里得算法

对于两个数 $a, b$ ，有 $\gcd(a, b) = \gcd(b, a \bmod b)$。

证明 :

假设 $a = kb + c$， 对于 $a ,b$ 的公因数 $d$ ，因为 $d | a, d | b$， 所以 $d | c$， 所以 $a , b$ 的公因数均为 $c$ 的约数, 反之 $b, c$ 的公约数同时也是 $a$ 的约数， 所以公约数集合相同，得证。

即可递归实现。

int gcd(int a, int b)
{
    if(!a || !b)return a + b;
    else return gcd(b, a % b);
}

最小公倍数

对于两个数 $a, b$， 有 $lcm(a, b) \times \gcd(a, b) = a \times b$， 由算术基本定理可得。

更相减损法

对于两个数 $a, b$， 有 $\gcd(a, b) = \gcd(b, a - b)$， 证明同欧几里得算法。

拓展欧几里得算法

拓展欧几里得算法用于求解形如 $ax + by = \gcd(a, b)$ 方程的一组可行解，其推导过程如下，

$$\because \gcd(a, b) = \gcd(b, a \bmod b) \\ \therefore ax + by = \gcd(a, b) = \gcd(b, a \bmod b) \\$$

考虑递归下去，当 $b = 0$ 时， 此时解为 $x = 1, y = 0$，然后对于当前解与上次迭代的关系为，

$$bx + (a \bmod b) y = \gcd(b, a \bmod b) \\ bx + (a - \lfloor \frac{a}{b} \rfloor \times b) y = \gcd(a, b) \\$$

整理得，

$$ay + b(x - \lfloor \frac{a}{b} \rfloor \times y) = \gcd(a, b)$$

递归求解即可，

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

求出的 $x_0, y_0$ 为一组特解，通解为 $x = x_0 + k \frac{b}{\gcd(a, b)}, y = y_0 - k \frac{a}{\gcd(a, b)}$ 。

数论分块

求解 $\sum_{i = 1} ^ n \lfloor \frac{n}{i} \rfloor$， 复杂度 $O(\sqrt{n})$，对于连续的一段 $i$， 其值可能是相同的，假设左边界为 $l$ ， 可得右边界为 $\big \lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \big\rfloor$ 。

证明 :

设 $x = \lfloor \frac{n}{i} \rfloor$，有 $x \le \frac{n}{i}$

所以对于每个 $i$ 和其对应的 $\frac{n}{i}$， $\lfloor \frac{n}{x} \rfloor \ge \lfloor \frac{n}{\frac{n}{i}} \rfloor$， 即 $i \le \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$， 得证。

对于求解 $\sum_{i = 1} ^ n \lfloor \frac{n}{i} \rfloor$

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

欧拉函数

定义欧拉函数 $\varphi(n)$ 表示 $1$ 到 $n$ 中与 $n$ 互质的数的个数。

性质

假设将 $n$ 唯一分解为 $\prod_{i = 1} ^ {m} p_i ^ {k_i}$， 有 $\varphi(n) = n \prod_{i = 1} ^ m (1 - \frac{1}{p_i})$。

证明 :

$n$ 个数中是 $p_i$ 倍数的个数有 $\frac{n}{p_i}$ 个， $n - \sum_{i = 1} ^ m \frac{n}{p_i}$ 后， 会减去重复的部分，还要加上，使用容斥原理即可得证。

欧拉函数为积性函数。

对于任意正整数 $n$， 有 $n = \sum_{d | n} \varphi(d)$ 。

证明 :

设 $f(n) = \sum_{d \mid n} \varphi(d)$， $m \perp n$，根据欧拉函数的积性函数的性质有：

$$\begin{aligned} f(n) \times f(m) & = \sum_{i \mid n} \varphi(i) \sum_{j \mid m} \varphi(j) \\ & = \sum_{i \mid n} \sum_{j \mid m} \varphi(i) \varphi(j) \\ & = \sum_{i \mid n} \sum_{j \mid m} \varphi(ij) \\ & = \sum_{d \mid nm} \varphi(d) \\ & = f(nm) \end{aligned}$$

将 $n$ 质因数分解 $p_1 ^ {c_{1}} \times p_2 ^ {c_{2}} \times p_3 ^ {c_{3}} \times \cdots \times p_k ^ {c_{k}}$。

所以有，

$$f(n) = f(p_1 ^ {c_{1}}) \times f(p_2 ^ {c_{2}}) \times \cdots \times f(p_k ^ {c_{k}})$$

其中的每一项有：

$$f(p ^ c) = \sum_{i = 0}^ c \varphi(p^i) = p^c$$

所以得证：

$$f(n) = f(p_1 ^ {c_{1}}) \times f(p_2 ^ {c_{2}}) \times \cdots \times f(p_k ^ {c_{k}}) = \Pi_{i =1}^k p_i^{c_i} = n = \sum_{d \mid n} \varphi(d)$$

简单筛法

埃拉托斯特尼筛法

假如我们要筛出 小于或等于 $n$ 的所有质数， 单纯做 $n$ 次素性测试是达不到最优复杂度的。

首先考虑这样一种筛法， 对于任意一个大于 $1$ 的正整数，其倍数一定是合数，然后枚举即可。

for(int i = 2; i <= n; i++)
{
    if(!vis[i])prime[++cnt] = i;
    for(int j = i; i * j <= n; j++)
        vis[i * j] = 1;
}

时间复杂度为 $O(n \ln n)$。

欧拉筛

埃氏筛的过程中有的合数被标记了不止一次， 还可以进一步优化，让每个数只被其最小质因子标记一次，也就是欧拉筛。

for(int i = 2; i <= n; i++)
{
    if(!vis[i])prime[++cnt] = i;
    for(int j = 1; j <= cnt && prime[j] * i <= n; j++)
    {
        vis[prime[j] * i] = 1;
        if(i % prime[j] == 0)break;
    }
}

线性筛也可以用来筛积性函数，

筛欧拉函数，

phi[1] = 1;
for(int i = 2; i <= n; i++)
{
    if(!vis[i])
    {
        prime[++cnt] = i;
        phi[i] = i - 1;
    }
    for(int j = 1; j <= cnt && prime[j] * i <= n; j++)
    {
        vis[i * prime[j]] = 1;
        if(i % prime[j] == 0)
        {
            phi[i * prime[j]] = phi[i] * prime[j];
            break;
        }
        phi[i * prime[j]] = phi[i] * phi[prime[j]];
    }
}

筛莫比乌斯函数，

mu[1] = 1;
for(int i = 2; i <= n; i++)
{
    if(!vis[i])
    {
        prime[++cnt] = i;
        mu[i] = -1;
    }
    for(int j = 1; j <= cnt && prime[j] * i <= n; j++)
    {
        vis[i * prime[j]] = 1;
        if(i % prime[j] == 0)
        {
            mu[i * prime[j]] = 0;
            break;
        }
        mu[i * prime[j]] = -mu[i];
    }
}

筛约数个数函数

d[1] = 1;
for(int i = 2; i <= n; i++)
{
    if(!vis[i])
    {
        prime[++cnt] = i;
        d[i] = 2; c[i] = 1;
    }
    for(int j = 1; j <= cnt && prime[j] * i <= n; j++)
    {
        vis[i * prime[j]] = 1;
        if(i % prime[j] == 0)
        {
            c[i * prime[j]] = c[i] + 1;
            d[i * prime[j]] = d[i] + d[i] / (c[i] + 1);
            break;
        }
        c[i * prime[j]] = 1;
        d[i * prime[j]] = d[i] * d[prime[j]];
    }
}

Pollard Rho

Pollard Rho 可以用来快速分解非平凡因数， 相比朴素的 $O(\sqrt{n})$ 会快很多，但是是一个随机性算法， 实际运行效率不定。

随机选一个数来判断其是不是 $n$ 因数， 显然概率低， 是不可行的，但是我们可以利用生日悖论，采用组合随机采样的方法，来提高正确率。

首先考虑最大公约数一定是某个数的约数， 也就是说 $\forall k \in \mathbb{N} ^ {*}, \gcd(k, n) | n$ ，随机选取一个 $k$ 使得 $\gcd(k, n) > 1$ 就可以求得一个约数。

比如选取一个序列 $x_i$， 若有 $\gcd(|x_i - x_j|, n) > 1$， 则求得一个约数，但是这样比较的话，是 $O(n ^ 2)$ 的，还需要降低时间复杂度。

我们可以构造一伪随机函数， $f(x) = (x ^ 2 + c) \bmod n$ 来生成一个随机数序列， 其中 $c = rand()$， 为一个随机数。然后再随机取一个 $x_0$ ， 令 $x_i = f(x_{i - 1})$， 生成随机序列， 取相邻两项求 $\gcd$。

但是这个序列会出现循环节，需要进一步优化， 也就是需要找出循环节。

找循环节可以用一个简单的 $Floyd$ 判圈算法， 也就是类似 ”龟兔赛跑“， 一个以另一个两倍的速度去遍历， 相遇即为找到环。

但是由于求 $\gcd$ 的时间复杂度为 $O(\log n)$ 的频繁调用的话会导致算法变慢，此时可以乘法累计减少求 $\gcd$ 的次数，显然如果 $\gcd(a, b) > 1$ ， 则有 $\gcd(ac, b) > 1$, 又因为 $\gcd(ac, b) = \gcd(ac \bmod b, b)$， 所以我们可以把所有测试样本在模 $n$ 的意义下乘起来， 然后使用倍增优化，每次在路径上取一段区间 $[l, r]$， 每次取测试样本为 $|x_i - x_l|$ 这样每次累计的样本个数就为 $r - l + 1$ 个，减少了取 $\gcd$ 的次数。 样本长度建议选为 $127$ 。

下面是找一个数的最大质因子的方法，

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define i128 __int128_t

ll n, Max;

ll gcd(ll a, ll b)
{
    if(!a || !b)return a + b;
    else return gcd(b, a % b);
}

ll qpow(ll a, ll b, ll mod)
{
    ll t = 1;
    while(b != 0)
    {
        if(b & 1)t = (i128)t * a % mod;
        a = (i128)a * a % mod; b >>= 1;
    }
    return t;
}

bool miller_rabin(ll p)
{
    if(p < 2)return 0;
    if(p == 2 || p == 3)return 1;
    ll d = p - 1, r = 0;
    while(!(d & 1))r++, d >>= 1;
    for(int k = 1; k <= 10; k++)
    {
        ll a = rand() % (p - 2) + 2;
        ll x = qpow(a, d, p);
        if(x == 1 || x == p - 1)continue;
        for(int i = 1; i <= r; i++)
        {
            x = (i128)x * x % p;
            if(x == p - 1)break;
        }
        if(x != p - 1)return 0;
    }
    return 1;
}

ll pollard_rho(ll x)
{
    ll s = 0, t = 0, c = (ll)rand() % (x - 1) + 1;
    int step = 0, ed = 1; ll v = 1;
    for(ed = 1; ; ed <<= 1, s = t, v = 1)
    {
        for(step = 1; step <= ed; step++)
        {
            t = ((i128)t * t + c) % x;
            v = (i128)v * abs(t - s) % x;
            if(step % 127 == 0)
            {
                ll d = gcd(v, x);
                if(d > 1)return d;
            }
        }
        ll d = gcd(v, x); if(d > 1)return d;
    }
}

void get_fact(ll x)
{
    if(x <= Max || x < 2)return;
    if(miller_rabin(x))
        return void(Max = max(Max, x));
    ll p = x;
    while(p >= x)p = pollard_rho(x); // 找出 x 的一个约数， 将其分解
    while(x % p == 0)x /= p;
    get_fact(x); get_fact(p); // 分解成 x 和 p 然后继续分解
}

int main()
{
    srand(time(0));
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%lld", &n);
        Max = 0; get_fact(n);
        if(Max == n)printf("Prime\n");
        else printf("%lld\n", Max);
    }
    return 0;
}

裴蜀定理

设 $a, b$ 是不全为零的整数， 则存在整数 $x, y$ 使得 $ax + by = \gcd(a, b)$。

对于方程 $ax + by = c$ 若 $\gcd(a, b) \not | c$ 则方程无整数解。

欧拉定理

若 $\gcd(a, m) = 1$ ， 则 $a ^ {\varphi(m)} \equiv 1 \pmod m$

证明 :

跟费马小定理相似的证法， 构造一个与 $m$ 互质的数列， 为 $A_1, A_2, \cdots A_{\varphi(m)}, 1 \le A_i \le m$， 然后选取一个与 $m$ 互质的正整数 $a$ 有，

$$\prod_{i = 1} ^ {\varphi(m)} A_i \equiv \prod_{i = 1} ^ {\varphi(m)} (A_i \times a) \pmod p$$

不难得出其是一一对应的， $a ^ {\varphi(m)} \equiv 1 \pmod m$ 得证。

扩展欧拉定理 ：

$$a ^ b \equiv \left\{ \begin{aligned} &a ^ {b \bmod \varphi(m)} &\gcd(a, m) = 1 \\ &a ^ b &\gcd(a, m) \not = 1, b \le \varphi(m), \pmod m \\ &a ^ {b \bmod \varphi(m) + \varphi(m)} &\gcd(a, m) \not = 1, b \ge \varphi(m) \end{aligned} \right.$$

乘法逆元

对于一个线性同余方程 $ax \equiv 1 \pmod b$ ， 则 $x$ 称为 $a \bmod b$ 的逆元， 记作 $a ^ {-1}$ 。

费马小定理

若求 $a$ 在模 $p$ 下的逆元，且 $p$ 为质数，可以使用费马小定理。

$$\because a ^ {p - 1} \equiv 1 \pmod p \\ \therefore a ^ {p - 2} \equiv \frac{1}{a} \pmod p$$

扩展欧几里得算法

当 $p$ 不为质数时， 就不可以使用费马小定理， 假设 $a , m$ 互质。

$$\because ax \equiv 1 \pmod m \\ \therefore ax - my = 1$$

直接用扩展欧几里得方程解出的解即为乘法逆元。

线性求逆元

上述方法单次求逆元复杂度都是 $O(\log n)$ ， 存在线性递推的做法。

线性递推求逆元要求 $p$ 为质数。

设 $p = ki + r (r < i, 1 < i < p)$， 有，

$$ki + r \equiv 0 \pmod p$$

两边同时乘 $i ^ {-1}, r ^ {-1}$， 得，

$$i ^ {-1} r ^ {-1} (ki + r) \equiv 0 \pmod p$$

展开得，

$$i ^ {-1} + kr ^ {-1} \equiv 0 \pmod p$$

即，

$$i ^ {-1} \equiv -kr ^ {-1} \pmod p$$

根据设得 $p$ 可以得知

$$i ^ {-1} \equiv - \lfloor \frac{p}{i} \rfloor \times (p \bmod i) ^ {-1} \pmod p$$

又等价于

$$i ^ {-1} \equiv (p - \lfloor \frac{p}{i} \rfloor) \times (p \bmod i) ^ {-1} \pmod p$$

此时即可递推， $inv[1] = 1$ 。

中国剩余定理

中国剩余定理可以用来求解如下形式得一元线性同余方程组。其中 $n_1, n_2, \cdots , n_k$ 两两互质。

$$\left\{ \begin{aligned} &x \equiv a_1 \pmod m_1 \\ &x \equiv a_2 \pmod m_2 \\ & \vdots \\ &x \equiv a_n \pmod m_n \\ \end{aligned} \right.$$

主要是用构造的方式，设 $M = \prod_{i = 1} ^ n m_i, M_i = \frac{M}{m_i}$ ， 解即为 :

$$\sum_{i = 1} ^ n a_i M_i M_i ^ {-1} \pmod M$$

其中 $M_i ^ {-1}$ 为模 $m_i$ 意义下的逆元。

扩展中国剩余定理

当模数不两两互质时，假设有两个方程为 $x \equiv a_1 \pmod m_1, x \equiv a_2 \pmod m_2$。

将其转化为不定方程为 $x = m_1p + a_1 = m_2q + a_2$， 则有 $m_1p - m_2q = a_2 - a_1$。

然后用扩展欧几里得算法求出一组可行解 $p, q$。

构成一个新的同余方程为 $x \equiv b \pmod M$， 其中 $b = m_1p + a_1, M = lcm(m_1, m_2)$。

威尔逊定理

对于素数 $p$ 有 $(p - 1)! \equiv -1 \pmod p$。

证明 :

首先 $p = 2$ 时显然成立，然后讨论奇素数的情况， 此时 $1, 2, \cdots, p - 1$ 均存在逆元， 且一一对应，那么只需要将一个数与其逆元一一对应即可，那么显然 $(p - 1)! \bmod p = p - 1$，即 $(p - 1) ! \equiv -1 \pmod p$ 。

BSGS

BSGS(baby-step giant-step) 是用来解决形如

$$a^x \equiv b \quad (\bmod m)$$

的高次同余方程，其中 $a \perp m$

首先$0 \le x < m$（就$m$个不同的得数），设$x=A \sqrt{m}-B$，其中$0 \le A,B\le \sqrt{m}$，方程变为：

$$a^{A \sqrt{m}-B} \equiv b \quad (\bmod m)$$

由于 $a \perp m$移项可得：

$$a^{A \sqrt{m}} \equiv ba^{B} \quad (\bmod m)$$

由于$a,b,m$均已知可以考虑枚举$B$用$map$存储对应的值，然后再枚举$A$，检查$map$中是否有值对应

因为$A,B$均不大于$\sqrt{m}$，所以时间复杂度为$O(\sqrt{n})$。（没算$map$）

exBSGS

问题仍然是去解决一个形如

$$a^x \equiv b \quad (\bmod m)$$

的高次同余方程，但不保证$a \perp m$

考虑用扩展BSGS(exBSGS) 来解决这个问题

此时$a$和$m$不一定互质，我们可以将式子进一步化简为：

$$\frac{a^x}{\gcd(a,m)} \equiv \frac{b} {\gcd(a,m)} \quad (\bmod \frac{m}{\gcd(a,m)})$$

将左边提出一项

$$a^{x-1} \frac{a}{\gcd(a,m)} \equiv \frac{b} {\gcd(a,m)} \quad (\bmod \frac{m}{\gcd(a,m)})$$

接下来不断除以$\gcd(a,m)$直到$a$与$m$互质，然后用BSGS求解

由于最后我们将式子递归执行了$k$层，此时式子变为

$$a^{x-k} \frac{a^k}{\gcd^k(a,m)} \equiv \frac{b} {\gcd^k(a,m)} \quad (\bmod \frac{m}{\gcd^k(a,m)})$$

最后利用BSGS求解出$x$后应当再加上$k$，$x+k$即为该方程的解。

卢卡斯定理

卢卡斯定理用于求解大组合数取模的问题，其中模数要求为质数。

对于质数 $p$ ，有

$$\dbinom{n}{m} \bmod p = \dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \times \dbinom{n \bmod p}{m \bmod p} \bmod p$$

可以直接递归求解。

证明 :

考虑
$\dbinom{p}{n} \bmod p$ 的取值，注意到

$\dbinom{p}{n} = \frac{p!}{n!(p - n)!}$ ，分子的质因子分解中 $p$ 的次数恰好为 $1$ ，因此只有当 $n = 0$ 或 $n = p$ 的时候 $n!(p - n)!$ 的质因子分解中含有 $p$ ，因此
$\dbinom{p}{n} \bmod p = [n = 0 \vee n = p]$ 。进而我们可以得出

$$\begin{aligned} (a + b) ^ p &= \sum_{n = 0} ^ p \dbinom pn a ^ n b ^ {p - n}\\ &\equiv \sum _ {n = 0} ^ p [n = 0\vee n = p] a ^ n b ^ {p - n}\\ &\equiv a ^ p + b ^ p \pmod p \end{aligned}$$

注意过程中没有用到费马小定理，因此这一推导不仅适用于整数，亦适用于多项式。因此我们可以考虑二项式 $f^p(x)=(ax^n + bx^m)^p \bmod p$ 的结果

$$\begin{aligned} (ax^n + bx^m)^p &\equiv a^p x^{pn} + b^p x^{pm} \\ &\equiv ax^{pn} + bx^{pm}\\ &\equiv f(x^p) \end{aligned}$$

考虑二项式 $(1 + x) ^ n \bmod p$ ，那么
$\dbinom n m$ 就是求其在 $x ^ m$ 次项的取值。使用上述引理，我们可以得到

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

注意前者只有在 $p$ 的倍数位置才有取值，而后者最高次项为 $n \bmod p \le p - 1$，因此这两部分的卷积在任何一个位置只有最多一种方式贡献取值，即在前者部分取 p 的倍数次项，后者部分取剩余项，即

$$\dbinom{n}{m} \bmod p = \dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \times \dbinom{n\bmod p}{m\bmod p}\bmod p$$

扩展卢卡斯定理

对于 $p$ 不为质数的情况，就需要用到扩展卢卡斯定理。

对于 $\dbinom{n}{m} \bmod M$， 我们先将 $M$ 唯一分解， $M = \prod_{i = 1} ^ r p_i ^ {k_i}$， 然后构造一个同余方程组。

$$\left\{ \begin{aligned} &a_1 \equiv \dbinom{n}{m} \pmod {p_1 ^ {k_1}} \\ &a_2 \equiv \dbinom{n}{m} \pmod {p_2 ^ {k_2}} \\ &\vdots \\ &a_r \equiv \dbinom{n}{m} \pmod {p_r ^ {k_r}} \\ \end{aligned} \right.$$

先求每个方程的解，然后用中国剩余定理合并即可。

对于求解 $a \equiv \dbinom{n}{m} \pmod {p ^ k}$，

$$\because \dbinom{n}{m} = \frac{n!}{m!(n - m)!} \\ \therefore \dbinom{n}{m} \bmod p ^ k = \frac{n!}{m!(n - m)!} \bmod p ^ k$$

然后考虑分母如何计算，由于分母分子和模数不一定互质，考虑提出 $n!$ 中的 $p$ 的倍数。

$$n! = p ^ {\lfloor \frac{n}{p} \rfloor} \times \lfloor \frac{n}{p} \rfloor ! \times \prod_{p \not | i} ^ n i$$

前面的直接快速幂，$\lfloor \frac{n}{p} \rfloor !$ 直接递归计算。

后面不整除的数显然会出现循环节，也就是

$$\prod_{p \not | i} ^ n i = (\prod_{i = 1, p \not | i} ^ {p ^ k} i) ^ {\lfloor \frac{n}{p ^ k} \rfloor} (\prod_{i = p ^ k \frac{n}{p ^ k}, p \not | i} ^ n i)$$

分成了循环节和余项。

递归处理把 $p$ 的倍数处理完即可。

式子其实就是，

$$\frac{\frac{n!}{p ^ x}}{\frac{m!}{p ^ y}\frac{(n - m)!}{p ^ z}} p ^ {x - y - z} \bmod p ^ k$$

对于 $x - y - z$， 其实就是 $\sum_{i = 1} \lfloor \frac{n}{p ^ i} \rfloor$。

类欧几里得算法

类欧几里德算法是由洪华敦在 2016 年冬令营营员交流中提出的内容，其本质可以理解为，使用一个类似辗转相除法来做函数求和的过程。

问题1

设

$$\tag{1,1} f(a,b,c,n)= \sum_{i=0}^n \bigg\lfloor\frac{ai+b}{c} \bigg\rfloor$$

其中 $a,b,c,n \in \mathbb{Z}$ 。

一眼不可做，似乎像数论分块，但又好像不太行的样子。

$a,b,c,n$ 之间的关系也没给，那就分情况吧

首先考虑第一种情况 $a \ge c,b \ge c$，（也是最简单的一种情况）

此时式子可以进一步化简为 ：

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

此时我们把式子化为了一个含有 $f$ 的递归式，接下来 $a,b$ 必定会变得小于 $c$，还需讨论另一种情况

$a < c,b< c$ 时，这时候也不能用上面的方法，🤔

利用枚举贡献的方法，将式子化为 ：

$$\tag{1,3} f(a,b,c,n)=\sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{ai+b}{c} \rfloor -1} 1$$

似乎什么都没有做的样子。。

需要进一步化简：

$$\tag{1,4} \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{ai+b}{c} \rfloor -1} 1 = \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \bigg[j< \lfloor\frac{ai+b}{c} \rfloor \bigg]$$

改了第二层求和的上界，好像有点头绪了

现在限制我们的就是后面的条件表达式了，也许可以将转化为某种方便计算的形式:

$$\tag{1,5} \because j< \lfloor\frac{ai+b}{c} \rfloor \\ \therefore j\le \frac{ai+b}{c} -1 \\ \therefore jc\le ai+b-c \\ \therefore jc < ai+b-c+1\\ \therefore i>\frac{jc+c-b-1}{a} \\ \therefore i>\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor$$

这样的话原来的式子就变为了：

$$\tag{1,6} \begin{aligned} f(a,b,c,n) &= \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \Bigg[i>\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor \Bigg] \\ &= \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \sum_{i=0}^n \Bigg[i>\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor \Bigg] \\ &= \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \sum_{i=\lfloor\frac{jc+c-b-1}{a}\rfloor+1}^n1 \\ &=\sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} (n-\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor) \\ &= \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1}n- \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1}\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor \\ &= \lfloor\frac{an+b}{c} \rfloor n-f(c,c-b-1,a,\lfloor\frac{an+b}{c} \rfloor-1) \end{aligned}$$

将 $\lfloor\frac{an+b}{c} \rfloor$ 设为 $m$ 再整理一下，又得到一个递归式：

$$\tag{1,7} f(a,b,c,n)=mn-f(c,c-b-1,a,m-1)$$

综上（1,2）（1,6）：

$$\tag{1,8} f(a,b,c,n)= \left\{ \begin{aligned} & \frac{n(n+1)}{2} \lfloor \frac{a}{c} \rfloor+(n+1)\lfloor \frac{b}{c}\rfloor + f(a \bmod c,b\bmod c,c,n) &a\ge c\vee b \ge c\\ &\lfloor\frac{an+b}{c} \rfloor n-f(c,c-b-1,a,\lfloor\frac{an+b}{c} \rfloor-1) &a<c\land b<c \end{aligned} \right.$$

可以在 $O(\log n)$ 时间内求出。

问题2

设

$$\tag{2,1} g(a,b,c,n)= \sum_{i=0}^n i \bigg\lfloor\frac{ai+b}{c} \bigg\rfloor$$

其中 $a,b,c,n \in \mathbb{Z}$。

上个问题的升级版， 接着分情况，$a\ge c,b\ge c$ 时：

$$\tag{2,2} \begin{aligned} g(a,b,c,n) &= \sum_{i=0}^n i \bigg\lfloor\frac{ai+b}{c} \bigg\rfloor \\ &= \sum_{i=0}^n i \bigg\lfloor\frac{(\lfloor \frac{a}{c} \rfloor \times c +a \bmod c)i+\lfloor \frac{b}{c} \rfloor \times c +b \bmod c}{c} \bigg\rfloor \\ &= \sum_{i=0}^n i \bigg(\lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c}\rfloor +\bigg\lfloor \frac{(a\bmod c)i+b \bmod c}{c} \bigg\rfloor \bigg) \\ &=\sum_{i=0}^n \lfloor \frac{a}{c} \rfloor i^2+\sum_{i=0}^n \lfloor \frac{b}{c}\rfloor i +\sum_{i=0}^n \bigg\lfloor \frac{(a\bmod c)i+b \bmod c}{c} \bigg\rfloor i \\ &= \frac{n(n+1)(2n+1)}{6} \lfloor \frac{a}{c} \rfloor+ \frac{n(n+1)}{2} \lfloor \frac{b}{c}\rfloor+g(a\bmod c,b\bmod c,c,n) \end{aligned}$$

看来我们完成了一半了（似乎不是）

$a<c,b<c$ 时，枚举贡献将式子化为：

$$\tag{2,3} g(a,b,c,n)=\sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{ai+b}{c} \rfloor -1} i$$

改变上界：

$$\tag{2,4} \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{ai+b}{c} \rfloor -1} i = \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} i \bigg[j< \lfloor\frac{ai+b}{c} \rfloor \bigg]$$

转化条件表达式：

$$\tag{2,5} \begin{aligned} g(a,b,c,n) &= \sum_{i=0}^n \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} i \Bigg[i>\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor \Bigg] \\ &= \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \sum_{i=0}^n i \Bigg[i>\bigg\lfloor \frac{jc+c-b-1}{a}\bigg\rfloor \Bigg] \\ &= \sum_{j=0}^{\lfloor\frac{an+b}{c} \rfloor -1} \sum_{i=\lfloor\frac{jc+c-b-1}{a}\rfloor+1}^n i \\ \end{aligned}$$

设 $k=\lfloor\frac{jc+c-b-1}{a}\rfloor,m=\lfloor \frac{an+b}{c}\rfloor$，接着化简：

$$\tag{2,6} \begin{aligned} g(a,b,c,n) &= \sum_{i=0}^{m-1}\sum_{k+1}^ni \\ &= \sum_{i=0}^{m-1}\frac{(n-k)(n+k+1)}{2} \\ &= \sum_{i=0}^{m-1}\frac{n^2+n-k^2-k}{2} \\ &= \frac{1}{2}\bigg(mn^2+mn-\sum_{j=0}^{m-1}(\lfloor\frac{jc+c-b-1}{a}\rfloor)^2-\sum_{i=0}^{m-1}\lfloor\frac{jc+c-b-1}{a}\rfloor\bigg) \end{aligned}$$

。。。好像化的没问题啊，出现了一个没见过的平方，先定义为 $h(a,b,c,n)$ 吧，整理一下得：

$$\tag{2,7} g(a,b,c,n)= \left\{ \begin{aligned} & \frac{n(n+1)(2n+1)}{6} \lfloor \frac{a}{c} \rfloor+ \frac{n(n+1)}{2} \lfloor \frac{b}{c}\rfloor+g(a\bmod c,b\bmod c,c,n) & a\ge c\vee b\ge c \\ & \frac{1}{2}\bigg( \bigg\lfloor\frac{an+b}{c}\bigg\rfloor n(n+1) - h(c,c-b-1,a,\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-1)-f(c,c-b-1,a,\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-1)\bigg) & a<c \land b<c \end{aligned} \right.$$

接下来解决带平方的问题。

问题3

设

$$\tag{3,1} h(a,b,c,n)=\sum_{i=0}^n \bigg(\bigg\lfloor \frac{ai+b}{c}\bigg\rfloor \bigg)^2$$

其中 $a,b,c,n \in \mathbb{Z}$。

上个问题还没有完全解决，需要解出 $h(a,b,c,n)$，（不就多了个平方嘛，轻车熟路了，别打了别打了）

$$\tag{3,2} \begin{aligned} h(a,b,c,n) &= \sum_{i=0}^n \bigg(\bigg\lfloor\frac{ai+b}{c} \bigg\rfloor\bigg)^2\\ &= \sum_{i=0}^n \bigg(\bigg\lfloor\frac{(\lfloor \frac{a}{c} \rfloor \times c +a \bmod c)i+\lfloor \frac{b}{c} \rfloor \times c +b \bmod c}{c} \bigg\rfloor \bigg)^2\\ &= \sum_{i=0}^n \bigg(\lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c}\rfloor +\bigg\lfloor \frac{(a\bmod c)i+b \bmod c}{c} \bigg\rfloor \bigg)^2 \\ \end{aligned}$$

手动多项式乘法！

原式变为：

$$\tag{3,3} 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)$$

接着考虑 $a<c,b<c$ 的情况，设 $k=\lfloor\frac{jc+c-b-1}{a}\rfloor,m=\lfloor \frac{an+b}{c}\rfloor$，

平方可以拆成：

$$\tag{3,3} n^2=2\frac{n(n+1)}{2}-n=\bigg( 2\sum_{i=0}^n i\bigg) -n$$

避免了出现 $\sum \times \sum$，数学技巧

$$\tag{3,4} \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}$$

接着化简前面的部分：

$$\tag{3,5} \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-1}(j+1)\sum_{i=0}^n\left[j<\left\lfloor \frac{ai+b}{c} \right\rfloor\right]\\ &=\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n[i>k]\\ &=\sum_{j=0}^{m-1}(j+1)(n-k)\\ &=\frac{1}{2}nm(m+1)-\sum_{j=0}^{m-1}(j+1)\left\lfloor \frac{jc+c-b-1}{a} \right\rfloor\\ &=\frac{1}{2}nm(m+1)-g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1) \end{aligned}$$

整理一下：

$$\tag{3,6} h(a,b,c,n)= \left\{ \begin{aligned} &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) & a\ge c \vee b\ge c \\ & n\lfloor \frac{an+b}{c}\rfloor(\lfloor \frac{an+b}{c}\rfloor+1)-2g(c,c-b-1,a,\lfloor \frac{an+b}{c}\rfloor-1)-2f(c,c-b-1,a,\lfloor \frac{an+b}{c}\rfloor-1)-f(a,b,c,n) & a<c \land b<c \end{aligned} \right.$$

时间复杂度均为 $O(\log n)$！

狄利克雷卷积

狄利克雷卷积是定义在数论函数间的二元运算。

数论函数，是指定义域为 $\mathbb{N}$ ，值域为 $\mathbb{C}$ ， 的一类函数，每个数论函数可以视为一个复数的序列。

定义式为：

$$\bigg(f \ast g\bigg) (n) = \sum_{d \mid n} f(d)g(\frac{n}{d}) (d \in \mathbb{N}) \\$$

也可以写为 ：

$$\bigg(f \ast g\bigg) (n) = \sum_{d \mid n} f(\frac{n}{d})g(d) (d \in \mathbb{N})$$

同时由于对称性，又可以写为 ：

$$\bigg(f \ast g\bigg) (n) = \sum_{xy=n} f(x)g(y) (x,y \in \mathbb{N})$$

“+” 定义为了数论函数直接的直接相加， " $\ast$ "，其实就是乘。

常见的数论函数

单位函数

$$\varepsilon (n) = \left[ n=1 \right]$$

幂函数

$$Id_k(n) = n^k$$

约数函数

$$\sigma(n) = \sum_{d \mid n} d^k (d \in \mathbb{N})$$

欧拉函数

$\varphi(n)$ 表示 $1 ~ n$ 中与 $n$ 互质的整数的个数有多少个

$$\varphi (n) = n \prod_{p|n}(1-\frac{1}{p}) (p \in \mathbb{P})$$

（容斥可证）

有趣的是上面所写的函数均为积性函数，其中单位函数和幂函数为完全积性函数。

相关定理

1. 若 $f$ ， $g$ 为积性函数，则 $f \ast g$ 也为积性函数
   证明：

$$设 gcd(a,b) =1 \\ \begin{aligned} \therefore \bigg(f \ast g\bigg)(a) \cdot (f \ast g) (b) &= \sum_{i \mid a} f(i) g(\frac{a}{i}) \cdot \sum_{j \mid b} f(j) g(\frac{b}{j}) \\ &= \sum_{i \mid a} \sum_{j \mid b} f(i) g(\frac{a}{i}) \cdot f(j) g(\frac{b}{j}) \\ &= \sum_{d \mid ab} f(d)g(\frac{ab}{d}) \\ &= (f \ast g) (ab) \\ \end{aligned}\\$$

用到了积性函数的性质

2. $f \ast g = g \ast f$

证明 ：

$$\begin{aligned} \bigg(f \ast g\bigg)(n) &= \sum_{ij=n} f(i)g(j) \\ &= \sum_{ji=n} f(j)g(i) \\ &= (g \ast j) (n) \end{aligned}$$

对称性。

3. $(f \ast g ) \ast h = f \ast (g \ast h)$

利用对称性的式子去拆开即可得证。

4. $f \ast (g+h) = f \ast g + f \ast h$

证明：

$$\begin{aligned} \bigg(f \ast (g + h )\bigg) (n) &= \sum_{ij=n} f(i)\bigg( g + h \bigg)(j) \\ &= \sum_{ij=n} f(i)\bigg[ g(j) + h(j) \bigg] \\ &= \sum_{ij=n} f(i)g(j) + f(i)h(j) \\ &= \sum_{ij=n} f(i)g(j) + \sum_{ij=n} f(i)h(j) \\ &= \bigg(f \ast g + f \ast h\bigg) (n) \end{aligned}$$

特殊的卷积

$$Id_k \ast 1 = \sigma_k \\$$

证明：

$$\begin{aligned} \bigg( Id_k \ast 1\bigg) (n) &= \sum_{d \mid n} Id_k (d) 1 (\frac{n}{d}) \\ &= \sum_{d \mid n} Id_k (d) \\ &= \sum_{d \mid n} d^k \\ &= \sigma (n) \end{aligned}$$

同时可以得到一个应用广泛的式子 ：

$$\bigg( f \ast 1 \bigg) (n) = \sum_{d \mid n} f(d)$$

$$\varphi \ast 1 = Id$$

证明 ：

$$\because \bigg( \varphi \ast 1 \bigg)(n) = \sum_{d \mid n} \varphi (d) \\ 将 n 拆分为 \prod p^k \\ \begin{aligned} \therefore \bigg( \varphi \ast 1 \bigg)(n) &= \bigg( \varphi \ast 1 \bigg)(\prod p^k) \\ &= \prod \bigg( \varphi \ast 1 \bigg)( p_i^{k_i}) \\ &= \prod \sum_{j=1}^{k_i}\varphi(p_i^j) \\ &= \prod p_i^{k_i} \\ &= n \\ \end{aligned}\\ \therefore \varphi \ast 1 =Id$$

$$1 \ast 1 = d$$

证明 ：

$$\begin{aligned} \bigg( 1 \ast 1 \bigg)(n) &= \sum_{d \mid n} 1(d) 1(\frac{n}{d}) \\ &= \sum_{d \mid n} 1 \\ &= d(n) \end{aligned}$$

上述的运算加以结合可以得到更多结论 。

狄利克雷卷积逆

需要用到单位元，有 ：

$$\bigg(f \ast \varepsilon \bigg)(n) = \sum_{d \mid n} \varepsilon(d)f(\frac{n}{d}) =f (n)$$

定义 ：

$$f \ast f^{-1} = \epsilon$$

即为狄利克雷卷积逆

积性函数一定有狄利克雷逆，且它也是积性函数。

莫比乌斯反演

定义莫比乌斯函数为：

$$\mu (x) = \left\{ \begin{aligned} &1 &x=1 \\ &(-1)^k &\prod_{i=1}^k q_i=1 \\ &0&\max\left\{ q_i \right\} > 1 \end{aligned} \right.$$

推导

$$g=f \ast 1 \iff f= g \ast \mu$$

也就是 ：

$$f(n) = \sum_{d \mid n} g(d) \iff g(n) = \sum_{d \mid n} \mu(d) f( \frac{n}{d})$$

莫比乌斯函数的性质：

$$\sum_{d \mid n} ^n \mu(d) = [n=1]$$

接下来证明莫比乌斯反演定理 ：

$$\begin{aligned} &f(n)=\sum_{d \mid n}g(d)=\sum_{d \mid n}g(\frac{n}{d})\\ &\sum_{d \mid n} \mu(d)f(\frac{n}{d})=\sum_{d\mid n}\mu(d) \sum_{d_1 \mid \frac{n}{d}}g(d_1) \\ &\sum_{d \mid n}\sum_{d_1 \mid \frac{n}{d}} \mu(d)g(d_1) \\ &= \sum_{d_1 \mid n} \sum_{d \mid \frac{n}{d_1}}\mu(d)g(d_1) \\ &= \sum_{d_1 \mid n} g(d_1) \sum_{d \mid \frac{n}{d_1}} \mu(d) \\ &=g(n) \\ \end{aligned}$$

上述仅为充分性证明，必要性证明逆推即可。

杜教筛

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

对于数论函数 $f$ ， 要求计算 $S(n) = \sum_{i=1}^n f(i)$ 。

首先构造一个 $S(n)$ 关于 $S(\left\lfloor\frac{n}{i}\right\rfloor)$ 的递推式

对于任意一个数论函数 $g$ ，必须满足

$$\sum_{i=1}^n \sum_{d \mid i}g(d)f(\frac{i}{d})= \sum_{i=1}^ng(i)S(\left\lfloor\frac{n}{i}\right\rfloor) \iff \sum_{i=1}^n(f \ast g)(i) = \sum_{i=1}^ng(i)S(\left\lfloor\frac{n}{i}\right\rfloor)$$

简单的证明：

$$\sum_{i=1}^n \sum_{d \mid i}g(d)f(\frac{i}{d})\\ = \sum_{i=1}^n\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor} g(i)f(j)\\ = \sum_{i=1}^ng(i)\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor} f(j)\\ = \sum_{i=1}^ng(i)S(\left\lfloor\frac{n}{i}\right\rfloor) \\$$

求出递推式

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

可以用数论分块对后半部分快速求出结果。

对于一些筛法的小技巧：

对于比较大的数据时，筛法在筛前半段时花费的时间显然是比较长的，这时我们可以直接线性筛一遍先记录下来，在求后半段时就可以省下大部分时间，称为根号分治。

Powerful Number 筛

Powerful Number 筛类似于杜教筛，一样可以解决积性函数的前缀和。

要求为 :

存在一个函数 $g$ 满足 :

• $g$ 是积性函数
• $g$ 易求前缀和
• 对于质数 $p$ ， $f(p) = g(p)$

现在即可求 $\sum_{i = 1} ^ n f(i)$ 。

对于所有正整数 $n$， 记 $n$ 的质因数分解为 $n = \prod_{i = 1} ^ m p_i ^ {e_i}$。 $n$ 是 PN 当球仅当 $\forall 1 \le i \le m, e_i > 1$ 。

所有 PN 都可以表示成 $a ^ 2 b ^ 3$ 的形式，由此可得 $n$ 以内的 PN 至多有 $O(\sqrt n)$ 个。

对于求解 $F(n) = \sum_{i = 1} ^ n f(i)$， 首先构造出一个积性函数 $g$ ，设 $G(n) = \sum_{i = 1} ^ n g(i)$ 。

然后再去构造一个积性函数 $h$ ，满足 $f = g \ast h$，对于素数 $p$， 有 $f(p) = g(1)h(p) + g(p)h(1) = h(p) + g(p)$，即 $h(p) = 0$。

根据 $h(p) = 0$ 和 $h$ 是积性函数可以推出对于非 PN 的数 $n$ 有 $h(n) = 0$ ，也就是说 $h$ 在非 PN 处值为零。

然后就是推导 $F(n)$，

$$\begin{aligned} F(n) &= \sum_{i = 1} ^ n f(i) \\ &= \sum_{i = 1} ^ n \sum_{d | i} h(d) g(\frac{i}{d}) \\ &= \sum_{d = 1} ^ n h(d) \sum_{i = 1} ^ {\lfloor \frac{n}{d} \rfloor} g(i) \\ &= \sum_{d = 1} ^ n h(d) G(\lfloor \frac{n}{d} \rfloor) \\ &= \sum_{d = 1, d \ \mathrm{is} \ \mathrm{PN}} ^ n h(d) G(\lfloor \frac{n}{d} \rfloor) \end{aligned}$$

然后 $O(\sqrt{n})$ 找出所有 PN 计算 $h$， $h$ 的值其实只需要计算 $h (p ^ c)$ 的值即可。

对于计算 $h(p ^ c)$，有两种方法，一种是根据公式计算，直接找出 $h(p ^ c)$ 仅与 $p, c$ 有关的计算公式，另一种是根据 $f = g \ast h$ 有 $f(p ^ c) = \sum_{i = 0} ^ c = g(p ^ i) h(p ^ {c - i})$，移项即可得出， $h(p ^ c) = f(p ^ c) - \sum_{i = 1} ^ c g(p ^ i) h(p ^ {c - i})$ ，就可以直接枚举素数 $p$ 再枚举指数 $c$ 求解出所有 $h (p ^ c)$。

Min_25 筛

Min_25 筛可以在 $O(\frac{n ^ {\frac{3}{4}}}{\log n})$ 的时间复杂度下求出积性函数的前缀和。

其要求 $f(p)$ 是一个关于 $p$ 的项数较少的多项式或可以快速求值， $f(p ^ c)$ 可以快速求值。

记号

如无特别说明，本节中所有记为 $p$ 的变量的取值集合均为全体质数。

• $x / y := \left\lfloor\frac{x}{y}\right\rfloor$
• $\operatorname{isprime}(n) := [ |\{d : d \mid n\}| = 2 ]$ ，即 n 为质数时其值为 $1$ ，否则为 $0$。
• $p_{k}$ ：全体质数中第 $k$ 小的质数（如：$p_{1} = 2, p_{2} = 3$）。特别地，令 $p_{0} = 1$ 。
• $\operatorname{lpf}(n) := [1 < n] \min\{p : p \mid n\} + [1 = n]$ ，即 $n$ 的最小质因数。特别地，$n=1$ 时，其值为 $1$。
• $F_{\mathrm{prime}}(n) := \sum_{2 \le p \le n} f(p)$
• $F_{k}(n) := \sum_{i = 2}^{n} [p_{k} \le \operatorname{lpf}(i)] f(i)$

解释

观察 $F_{k}(n)$ 的定义，可以发现答案即为 $F_{1}(n) + f(1) = F_{1}(n) + 1$ 。

考虑如何求出 $F_{k}(n)$ 。通过枚举每个 $i$ 的最小质因子及其次数可以得到递推式：

$$\begin{aligned} F_{k}(n) &= \sum_{i = 2}^{n} [p_{k} \le \operatorname{lpf}(i)] f(i) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c} \le n}} f\left(p_{i}^{c}\right) ([c > 1] + F_{i + 1}\left(n / p_{i}^{c}\right)) + \sum_{\substack{k \le i \\ p_{i} \le n}} f(p_{i}) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c} \le n}} f\left(p_{i}^{c}\right) ([c > 1] + F_{i + 1}\left(n / p_{i}^{c}\right)) + F_{\mathrm{prime}}(n) - F_{\mathrm{prime}}(p_{k - 1}) \\ &= \sum_{\substack{k \le i \\ p_{i}^{2} \le n}} \sum_{\substack{c \ge 1 \\ p_{i}^{c + 1} \le n}} \left(f\left(p_{i}^{c}\right) F_{i + 1}\left(n / p_{i}^{c}\right) + f\left(p_{i}^{c + 1}\right)\right) + F_{\mathrm{prime}}(n) - F_{\mathrm{prime}}(p_{k - 1}) \end{aligned}$$

最后一步推导基于这样一个事实：对于满足

$p_{i}^{c} \le n < p_{i}^{c + 1}$ 的 c，有 $p_{i}^{c + 1} > n \iff n / p_{i}^{c} < p_{i} < p_{i + 1}$，故 $F_{i + 1}\left(n / p_{i}^{c}\right) = 0$。

其边界值即为 $F_{k}(n) = 0 (p_{k} > n)$。

假设现在已经求出了所有的 $F_{\mathrm{prime}}(n)$，那么有两种方式可以求出所有的 $F_{k}(n)$ ：

直接按照递推式计算。

从大到小枚举 $p$ 转移，仅当 $p^{2} < n$ 时转移增加值不为零，故按照递推式后缀和优化即可。

现在考虑如何计算 $F_{\mathrm{prime}}{(n)}$。

观察求 $F_{k}(n)$ 的过程，容易发现 $F_{\mathrm{prime}}$ 有且仅有 $1, 2, \dots, \left\lfloor\sqrt{n}\right\rfloor, n / \sqrt{n}, \dots, n / 2, n$ 这 $O(\sqrt{n})$ 处的点值是有用的。
一般情况下，$f(p)$ 是一个关于 $p$ 的低次多项式，可以表示为 $f(p) = \sum a_{i} p^{c_{i}}$ 。

那么对于每个 $p^{c_{i}}$ ，其对 $F_{\mathrm{prime}}(n)$ 的贡献即为 $a_{i} \sum_{2 \le p \le n} p^{c_{i}}$ 。

分开考虑每个 $p^{c_{i}}$ 的贡献，问题就转变为了：给定 $n, s, g(p) = p^{s}$ ，对所有的 $m = n / i$ ，求 $\sum_{p \le m} g(p)$。

Notice：$g(p) = p^{s}$ 是完全积性函数！

于是设 $G_{k}(n) := \sum_{i = 1}^{n} \left[p_{k} < \operatorname{lpf}(i) \lor \operatorname{isprime}(i)\right] g(i)$，即埃筛第 $k$ 轮筛完后剩下的数的 $g$ 值之和。

对于一个合数 $x$，必定有 $\operatorname{lpf}(x) \le \sqrt{x}，则 F_{\mathrm{prime}} = G_{\left\lfloor\sqrt{n}\right\rfloor}$，故只需筛到 $G_{\left\lfloor\sqrt{n}\right\rfloor}$ 即可。

考虑 $G$ 的边界值，显然为 $G_{0}(n) = \sum_{i = 2}^{n} g(i)$。（还记得吗？特别约定了 $p_{0} = 1$）

对于转移，考虑埃筛的过程，分开讨论每部分的贡献，有：

对于 $n < p_{k}^{2}$ 的部分，$G$ 值不变，即 $G_{k}(n) = G_{k - 1}(n)$。

对于 $p_{k}^{2} \le n$ 的部分，被筛掉的数必有质因子 $p_{k}$，即 $-g(p_{k}) G_{k - 1}(n / p_{k})$。

对于第二部分，由于 $p_{k}^{2} \le n \iff p_{k} \le n / p_{k}$，故会有 $\operatorname{lpf}(i) < p_{k}$ 的 $i$ 被减去。这部分应当加回来，即 $g(p_{k}) G_{k - 1}(p_{k - 1})$。

则有：

$$G_{k}(n) = G_{k - 1}(n) - \left[p_{k}^{2} \le n\right] g(p_{k}) (G_{k - 1}(n / p_{k}) - G_{k - 1}(p_{k - 1}))$$

贝尔级数

对于积性函数 $f(n)$ ，定义其在质数 $p$ 意义下的贝尔级数为 :

$$F_p(x) = \sum_{i = 0} ^ {\infty} f(p ^ i) x ^ i$$

相当于是把狄利克雷卷积变成了一般多项式卷积。

两个数论函数做狄利克雷卷积卷积，其贝尔级数相乘。

常见的贝尔级数，

• $e \Rightarrow 1$
• $I \Rightarrow \sum_{i = 0} ^ {\infty} x ^ i = \frac{1}{x}$
• $id_k \Rightarrow \sum_{i = 0} ^ {\infty} p^ {ik} x ^ i = \frac{1}{1 - p ^ k x}$
• $\mu \Rightarrow 1 - x$
• $d \Rightarrow \sum_{i = 0} ^ {\infty} (i + 1) x ^ i = \frac{1}{(1 - x) ^ 2} \Rightarrow I \ast I = d$
• $\sigma \Rightarrow \sum_{i = 0} ^ {\infty} x ^ i \sum_{j = 0} ^ i p ^ {jk} = \frac{1}{(1 - x)(1 - p ^ k x)} \Rightarrow I \ast id_k = \sigma_k$
• $\varphi \Rightarrow 1 + \sum_{i = 1} ^ {\infty} p ^ i (1 - \frac{1}{p}) x ^ i = \frac{1 - x}{1 - px} \Rightarrow \varphi \ast I = id$
• $w(n) = 2 ^ {k(n)}$， $k(n)$ 为不同质因子个数， $w \Rightarrow 1 + \sum_{i = 1} ^ {\infty} 2 x ^ i = \frac{1 + 1}{1 - x} \Rightarrow w = \mu ^ 2 \ast I$

常用在筛法中构造卷积。