数学杂项

整理一些小知识点

数论小函数

积性函数

• $\varphi$
• $\mu$
• $\sigma_k(n) = \sum\limits_{d \mid n} d^k$
• $d$ 因数个数函数 $\sigma_0$
• $\varepsilon(n) = [n = 1]$ 单位函数 完全积性
• $I(n) = 1$ 完全积性
• $id(n) = n$ 完全积性

性质

$\varphi$

$n=p_1^{\alpha_1} \cdots p_s^{\alpha_s}$ 对 $n$ 唯一分解

$$\varphi(n) = n \prod\limits_{i=1}^s (1 - \frac{1}{p_i}) \\ n = \sum\limits_{d \mid n} \varphi(d)$$

$\mu$

$\mu$ 与 $\varphi$

$$\varphi = n\sum\limits_{d \mid n} \frac {\mu(d)}{d}$$

$\mu$ 与 $d$ 的

$$d(i j)=\sum_{x \mid i} \sum_{y \mid j}[\operatorname{gcd}(x, y)=1]$$

卷积

$\varphi*1 = Id$

$\mu * 1 = \varepsilon$

$\sigma_k=Id_k*1$

常见反演

莫比乌斯反演

\begin{align} &\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} [gcd(i,j) == 1] \nonumber \\ =&\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d \mid gcd(i,j)} \mu(d)\nonumber \\ =&\sum\limits_{d=1}^n \mu(d) \sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} 1 \nonumber \\ =&\sum\limits_{d=1}^n \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor \nonumber \end{align}

欧拉反演

\begin{align} &\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} gcd(i,j)\nonumber \\ =&\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d \mid gcd(i,j)} \varphi(d)\nonumber \\ =&\sum\limits_{d=1}^n \varphi(d) \sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{n}{d} \rfloor} 1 \nonumber \\ =&\sum\limits_{d=1}^n \varphi(d) \left\lfloor \frac{n}{d} \right\rfloor ^2 \nonumber \end{align}

狄利克雷前缀和

$$f(i) = \sum\limits_{d\mid i} g(i)$$

类似 癌氏筛 可以在 $O(n\log\log n)$ 内解决这样的问题

先筛个素数 然后用 $g(i)$ 更新 $f(i)$

code

1
2
3
4
5

for(int i = 1; i <= cnt; i++)
{
    for(int j = 1; j * prime[i] <= n; j++)
    g[p[i] * j] += g[j]; 
}

类似的 还有后缀和

$$f(i) = \sum\limits_{i\mid d} g(i)$$

倒序枚举

1
2
3
4
5

for(int i = 1; i <= cnt; i++)
{
    for(int j = n/prime[i]; j; j--)
   	g[p[i] * j] += g[j]; 
}

差不多的 可以用 $f(i)$ 求 $g(i)$ 两级反转

1
2
3
4
5

for(int i = cnt; i; i--)
{
    for(int j  = n/prime[i]; j; j--)
    f[j * prime[i]] -= f[j];
}

筛子

欧拉筛

线性 $O(n)$ 筛质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void get_prime()
{
	isp[1] = mu[1] = phi[1] = 1;
	for (int i = 2; i <= maxn; i++)
	{
		if (!isp[i]) { prime[++cnt] = i; mu[i] = -1; phi[i] = i - 1; }
		for(int j = 1;j <= cnt && i*prime[j] <= MAXN-5; j++)
        {
            isp[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[i * prime[j]] = -mu[i];
        }
	}
}

杜教筛

可以在较拉的亚线性复杂度内求出积性函数前缀和

现在我们要求 $f$ 的前缀和 $S(n)$，我们先构造另一个畸性函数 $g$，从他俩的卷积的前缀和入手。

\begin{align} \sum\limits_{i = 1}^n f*g &= \sum\limits_{i = 1}^n \sum\limits_{d \mid i} f(d) * g (\frac id) \nonumber\\ &= \sum\limits_{d = 1}^n g(d) \cdot \sum\limits_{i = 1}^{\frac nd} f(i) \nonumber\\ &= \sum\limits_{d = 1}^n g(d) \cdot S(\frac nd) \nonumber \end{align}

对卷积整前缀和，然后我们把 $g(1)$ 提出来

\begin{align} g(1)S(n) &+ \sum\limits_{d = 2}^n g(d)S(\frac nd) =\sum\limits_i^n f*g \nonumber\\ S(n) &=\frac{\sum\limits_i^n f*g - \sum\limits_{d = 2}^n g(d)S(\frac nd)}{g(1)} \nonumber \end{align}

我们把它整成了递归形式，后面可以用数论分块，只要能找到合适的 $g$ 能快速求出 $f*g$ 就行辣

小数据欧拉筛，记忆化一下

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

ll Sum_mu(ll n)
{
	if (n <= maxn) return mu[n];
	if (S_mu.count(n)) return S_mu[n];
	ll l = 2, r, res = 1;
	while(l <= n)
	{
		r = n / (n / l);
		res -= 1LL*(r - l + 1) * Sum_mu(n/l);
		l = r + 1;
	}
	return S_mu[n] = res;
}

ll Sum_phi(ll n)
{
	if (n <= maxn) return phi[n];
	if (S_phi.count(n)) return S_phi[n];
	ll l = 2, r, res = n * (n+1) /2;
	while (l <= n)
	{
		r = n / (n / l);
		res -= 1LL*(r - l + 1) * Sum_phi(n/l);
		l = r + 1;
	}
	return S_phi[n] = res;
}

CRT

求解同余方程组，适用于模数两两互质的情况

$$\left\{\begin{matrix} x \equiv a_1 \; (mod \ p_1)\\ x \equiv a_2 \; (mod \ p_2)\\ \vdots \\ x \equiv a_n \; (mod \ p_n)\\ \end{matrix}\right.$$

ExCRT