整除与约数

约数（因数）：若 $a \mid b$，则称 $b$ 是 $a$ 的倍数，$a$ 是 $b$ 的约数。

gcd 和 lcm

定义：一组整数的公约数，是指同时是这组数中每一个数的约数的数。$1$ 是任意一组数的公约数，最大公约数（Greatest Common Divisor，$\gcd$）是指所有公约数里面最大的一个。

性质

• $\forall a,b \in \mathbb{N}$，如果 $\gcd(a,b)=1$，则称 $a, b$ 互质。

欧几里德算法

114514。

积性函数

素数与合数

void get_primes(int x) {
    memset(notp, 0, sizeof notp);
    for (int i = 2; i <= n; i ++ ) {
        if (!notp[i]) {
            pri[ ++ pcnt] = i;
            for (int j = i; j <= n / i; j ++ ) notp[i * j] = true;
        }
    }
}

void get_primes(int x) {
    memset(notp, 0, sizeof notp);
    notp[1] = true;
    for (int i = 2; i <= x; i ++ ) {
        if (!notp[i]) pri[ ++ pcnt] = i;
        for (int j = 1; i * pri[j] <= x && j <= pcnt; j ++ ) {
            notp[i * pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }
}

算术基本定理

欧拉函数

前置知识：

• 整除与约数

• 互质

• 积性函数

• 素数与合数

• 算术基本定理

定义：$1\sim N$ 中与 $N$ 互质的数的个数，记为 $\varphi(N)$。

性质

1. 若 $p$ 为质数，$\varphi(p)=p-1$。

证明：质数与 $1 \sim p-1$ 中的所有数字都互质。

2. $\forall n>1$，$1 \sim x$ 中与 $n$ 互质的数的和为 $n \times \varphi(x)/2$。

3. 若 $p$ 为质数，$x=p^c$，则 $\varphi(x)=p^{c-1} \times (p-1)$。

4. 若 $p,q$ 互质，则 $\varphi(p\times q)=\varphi(p)\times\varphi(q)$，即 $\varphi$ 是积性函数。

5. 对于一个正整数 $x$，将其质因数分解，$p$ 是 $x$ 的质因子：$x=p_1^{c_1}\times p_2^{c_2}\times p_3^{c_3}\times \dots \times p_k^{c_k}$。

$$\varphi(x)=x \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \dots \times \frac{p_m-1}{p_m} = x \times \prod_{p \mid x}(1 - \frac{1}{p})$$

证明（推导）：

$$\varphi(x) = \varphi(\prod_{p \mid x}p^{c}) = \prod_{p \mid x}\varphi(p^{c}) \\ \varphi(x) = \prod_{p \mid x}p^{c-1}\times(p-1) \\ \varphi(x) = \prod_{p \mid x}p^{c-1}\times p \times (p-1) / p = \prod_{p \mid x}p^c\times\frac{p-1}{p} \\ \varphi(x) = x\times\prod_{p \mid x}\frac{p-1}{p}=x\times\prod_{p \mid x}(1-\frac{1}{p}) \\$$

证明（容斥原理）：

先鸽了。

Tips 提示：由于浮点数有误差，使用公式计算欧拉函数时一般使用 $x \times \prod_{质数 \ p \mid x}\frac{p-1}{p}$。

6. 对于一个质数 $p$，如果有 $p \mid x$，那么 $\varphi(x \times p)=\varphi(x) \times p$。

证明：由于 $p \mid x$，所以 $x$ 的质因子包括 $p$，只是 $p$ 的指数不同，结合上面推导出的公式，这个 $p$，将会乘到 $x$ 上，$x$ 将会变成 $x \times p$，即 $\varphi(x \times p)=\varphi(x) \times p$。

7. 对于一个质数 $p$，如果有 $p \nmid x$，那么 $\varphi(x \times p)=\varphi(x) \times (p-1)$。

证明 1：由于 $p \nmid x$，所以 $x$ 的质因子里没有 $p$，$x$ 会变成 $x \times p$，$x$ 的质因子会增加一个 $p$，原式会再乘上一个 $\frac{p-1}{p}$，即 $\varphi(x \times p)=\varphi(x) \times p \times \frac{p-1}{p}=\varphi(x) \times (p-1)$。

证明 2：$\varphi(x \times p)=\varphi(x) \times \varphi(p)=\varphi(x) \times (p-1)。$

8. $\sum_{d \mid x}\varphi(d)=n$。

求欧拉函数

试除法

求 $x$ 的欧拉函数：将 $x$ 质因数分解，用 $res$ 记录 $x$ 的欧拉函数，根据公式 $\varphi(x) = x \times \prod_{质数 \ p \mid x}\frac{p-1}{p}$，初始时 $res=x$，之后每找到一个质因子 $p$，$res = res / p \times (p-1)$。时间复杂度 $O(\sqrt x)$。

int getphi(int x) {
    int res = x;
    for (int i = 2; i * i <= x; i ++ ) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

埃氏筛

void euler(int n) {
    for (int i = 1; i <= n; i ++ ) phi[i] = i;
    for (int i = 2; i <= n; i ++ ) {
        if (phi[i] == i) {
            for (int j = i; j <= n; j += i) {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}

线性筛

void euler(int x) {
    memset(notp, 0, sizeof notp);
    notp[1] = true;
    phi[1] = 1;
    for (int i = 2; i <= x; i ++ ) {
        if (!notp[i]) pri[ ++ pcnt] = i, phi[i] = i - 1;
        for (int j = 1; i * pri[j] <= x && j <= pcnt; j ++ ) {
            notp[i * pri[j]] = true;
            if (i % pri[j]) phi[i * pri[j]] = phi[i] * phi[pri[j]];
            else {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
        }
    }
}

同余

取模运算

设 $a \in \mathbb{Z}, b \in \mathbb{N^*}$，定义：

$$a \ \text{mod} \ b = \begin{cases} a-\frac{a}{n} \times n \hspace{2.5em} a \ge 0 \\ -(-a \bmod b) \hspace{1.1em} a < 0 \end{cases}$$

这与 C++ 中的取模运算符的行为一致。

定义

若 $(a-b) \bmod n=0$，则称 $a$ 和 $b$ 同余，记为 $a \equiv b \pmod n$ 读作 $a$ 和 $b$ 在模 $n$ 的意义下同余。

性质

1. 反身性，自反性，传递性

2. 如果 $a \equiv b \pmod{m}$，$c \equiv d \pmod m$，则有 $a \pm c \equiv b \pm d \pmod m$。

3. 如果 $a \equiv b \pmod m$，$c \equiv d \pmod m$，则有 $ac \equiv bd \pmod m$。

4. 如果 $a \equiv b \pmod m$，则有 $a^x \equiv b^x \pmod m$。

5. 如果 $ac \equiv bc \pmod m$，则有 $a\equiv b \pmod{\frac{m}{gcd(m, c)}}$

费马小定理

若 $p$ 是一个质数，且正整数 $a$ 满足 $a \bot p$，则 $a^{p-1}\equiv 1 \pmod{p}$。

其逆否命题是：若 $a \bot p, a^{p-1} \not \equiv 1 \pmod p$，则 $p$ 不是质数。

证明：
假设 $a^{p} \equiv a \pmod p$ 成立，则
$(a+1)^{p}=a+\binom{p}{1}a+\binom{p}{2}a+...+\binom{p}{p-1}a+1$
由于 $\binom{p}{q}=\frac{p!}{q!(p-q)!}$，当 $q \in (0, p)$，有 $\binom{p}{q}a \equiv 0 \pmod p$
则 $(a+1)^{p}\equiv a+1 \pmod p$
显然有 $1^{p} \equiv 1 \pmod p$，则 $a^{p} \equiv a \pmod p$ 得证。
由于 $a \bot p$，所以 $a^{p-1}\equiv 1 \pmod p$。

欧拉定理

若正整数 $a, p$ 满足 $a \bot p$，则 $a^{\varphi(p)} \equiv 1 \pmod p$。

逆元

线性预处理逆元

$1 \sim n$ 的逆元

给定一个数列 $a_1, a_2 ... a_n$。

Exgcd

Miller-Rabin 素性检验

二次探测定理：

上述的算法效率太低，我们考察一个更高效的算法。

首先用到费马小定理：

若 $p$ 为质数，$a \bot p$，则 $a^{p-1} \equiv 1 \pmod p$。

其逆命题是：

若 $a \bot p, a^{p-1} \equiv 1 \pmod p$，则 $p$ 是质数。

然而这个逆命题是不成立的，对于一些合数，仍满足 $a^{x-1} \bmod p = 1$，这样的数叫费马伪素数。

可以考虑多随机几组 $a$，这样能排除大量的上述情况。

但是这并不等价于对于若干个 $a$， 若 $a^{p-1} \equiv 1\pmod p$，则 $p$ 是质数。

有些数满足 $\forall \ a \perp p, a^p \equiv 1\pmod p, a \ge 2$，被称为卡迈克尔数。

费马小定理来判断质数是错误的。我们考虑引入新的定理来提高检测的正确性。

二次探测定理：

若 $p$ 为质数, 则当 $x < p$ 时，$x^2 \equiv 1\pmod p$ 有且仅有解 $1$ 和 $p-1$。

我们同样写出逆否命题：

当 $x < p$ 时，若 $x^2 \equiv 1\pmod p$ 的解不只有 $1$ 和 $p-1$，则 $p$ 不为质数。

接下来就是 Miller Rabin 素性检验算法的流程：

对于要检验的数 $n$，我们设费马小定理中的指数 $p-1=d \times 2^{r}$，若 $r \ge 1$，根据二次探测定理，若 $(a^{\frac{p-1}{2}})^2 \equiv 1 \pmod p$ 的解不只有 $p-1$ 和 $1$ 的话，则 $p$ 不为质数，即判断 $a^{\frac{p-1}{2}}$ 是不是等于 $p-1$ 或 $1$，以此类推，重复 $r$ 轮即可。

注意到 $p$ 无法通过以 $p$ 为底的素性检验，所以你需要特判为质数的底数。

若单次乘法的复杂度为 $O(1)$，这样做的时间复杂度为 $O(k \log^2 n)$。

可以发现其实仍有优化空间，复杂度瓶颈在二次探测。我们考虑把二次探测的过程翻过来，把 $d \times 2^r \rightarrow d$ 变为 $d \rightarrow d \times 2^r$，我们只需要算出 $a^d$，然后平方 $r$ 次即可。复杂度 $O(k \log n)$。

当然我们还可以光速幂，不过这样只是常数上的优化了。

Miller Rabin 检验依旧有错误的概率。我们可以通过选取适合的底数，来避免这一情况的发生。

• 如果 $n < 2,047$，只需测试 $a = 2$；
• 如果 $n < 1,373,653$，只需测试 $a = 2$ 和 $3$；
• 如果 $n < 9,080,191$，只需测试 $a = 31$ 和 $73$；
• 如果 $n < 25,326,001$，只需测试 $a = 2, 3$ 和 $5$；
• 如果 $n < 3,215,031,751$，只需测试 $a = 2, 3, 5$ 和 $7$；
• 如果 $n < 4,759,123,141$，只需测试 $a = 2, 7$ 和 $61$；
• 如果 $n < 1,122,004,669,633$，只需测试 $a = 2, 13, 23$ 和 $1662803$；
• 如果 $n < 2,152,302,898,747$，只需测试 $a = 2, 3, 5, 7$ 和 $11$；
• 如果 $n < 3,474,749,660,383$，只需测试 $a = 2, 3, 5, 7, 11$ 和 $13$；
• 如果 $n < 341,550,071,728,321$，只需测试 $a = 2, 3, 5, 7, 11, 13$ 和 $17$；
• 如果 $n < 3,825,123,056,546,413,051$，只需测试 $a = 2, 3, 5, 7, 11, 13, 17, 19$ 和 $23$；
• 如果 $n < 18,446,744,073,709,551,616 = 2^{64}$，只需测试 $a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$ 和 $37$；
• 如果 $n < 318,665,857,834,031,151,167,461$，只需测试 $a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$ 和 $37$；
• 如果 $n < 3,317,044,064,679,887,385,961,981$，只需测试 $a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37$ 和 $41$。

这样选择底数可以保证 $100 \%$ 正确。

代码实现

const int pa[] = {2, 3, 5, 7, 11, 13, 17};

int qmul(int a, int b, int mod) {
	a %= mod, b %= mod;
	int c = (long double)a * b / mod;
	int d = a * b - mod * c;
	if (d < 0) return d + mod;
	if (d >= mod) return d - mod;
	return d;
}

int qpow(int a, int b, int mod) {
	int res = 1;
	for (; b; b >>= 1) {
		if (b & 1) res = qmul(res, a, mod);
		a = qmul(a, a, mod);
	}
	return res;
}

bool mrtest(int n, int a) {
	int d = n - 1, r = 0;
	while (d % 2 == 0) d >>= 1, ++ r;
	int x = qpow(a, d, n);
	if (x == 1) return true;
	for (int i = 0; i < r; i ++ ) {
		if (x == n - 1) return true;
		x = qmul(x, x, n);
	}
	return false;
}

bool isprime(int n) {
	if (n < 2) return false;
	for (int i = 0; i < 7; i ++ ) {
		if (n == pa[i]) return true;
		if (!mrtest(n, pa[i])) return false;
	}
	return true;
}