「Summary」数论究极整理

I’m good at making everything difficult!

前几天懒得写，只有累到今天来补一下。。。。。。

线性筛

咕掉埃氏筛

欧拉筛

即是线性筛，可以在$\Theta(n)$的时间复杂度里筛出质数。

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

积性函数

• 积性函数

  $$\forall x,y.\\ \gcd(x, y) = 1 \rightarrow f(x\times y)=f(x)\times f(y)$$

• 完全积性函数

  $$\forall x, y.\\f(x\times y) = f(x)\times f(y)$$

  对于积性函数，我们可以通过线性筛计算，下面给出一些常见的积性函数计算方法。

欧拉函数

定义:$\phi(n)=\sum_{i= 1}^n(\gcd(i, n) = 1)$

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

约数个数

定义:$d(n)=\sum_{i=1}^n((n\mod i) = 0)$

设$num(i)$为$i$的最小质因子出现次数。

约数个数定理

$$n=\prod_{i=1}^m p_i^{q_i}\\ \rightarrow d(n)=\prod_{i=1}^m(q_i + 1)$$

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

约数和

定义:$f(n)=\sum_{i = 1}^n((n\mod i) = 0)\times i$

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

欧拉定理

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

原根

阶：由欧拉定理可知，对 $a\in \mathbb{Z}$，$m\in\mathbb{N}^{*}$，若 $\gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv 1\pmod m$。

因此满足同余式 $a^n \equiv 1 \pmod m$ 的最小正整数 $n$ 存在，这个 $n$ 称作 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$。

性质

$$ a,a^2,a^3,...,a^{\delta_m(a)}模m不同余 $$ $$ 若a^n \equiv 1 \pmod m \rightarrow \delta_m(a)|n $$

威尔逊定理

当$p$时素数时,$(p-1)! \equiv p - 1\pmod p$

裴蜀定理

$\forall x, y$当$\gcd(x,y)|m$时,方程$k_1x+k_2y=m$有解。 ## 扩展欧几里得

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

CRT & ExCRT

扩展中国剩余定理用于求解模线性同余方程组。

其思想是依次合并两个方程直到剩下一个方程，就是解系。

void ExCRt () {
    int m1 = m[1], r1 = r[1];
    for (int i = 2; i <= n; i++) {
		int m2 = m[i], r2 = r[i];
        int k1, k2;
        int tmp = r2 - r1;
        int g = exgcd (k1, k2, m1, m2);
        if (tmp % g != 0) {
            printf ("-1\n");
            break;
        }
        exgcd (k1, k2, m1 / g, m2 / g);
        k1 = (tmp / g * k1) % (m2 / g);
        r1 += k1 * m1;
        m1 = m1 / g * m2;
        r1 = (r1 + m1) % m1;
    }
}

以上所有定理证明

先占坑。