Sakana~
0%

数论2：同余，欧拉函数，逆元

发表于 更新于 分类于

公式挂掉太丑了就看这里

数论2：同余，欧拉函数，逆元

同余

$$
a\equiv b (\mathrm{mod,,} m) \leftrightarrow m|b-a\
a\equiv b(\mathrm{mod,,} m), a\equiv b (\mathrm{mod,,}n)\rightarrow a\equiv b(\mathrm{mod,,}[m,n])\
\bbox[yellow]{
(k,m)=d, ka\equiv ka’(\mathrm{mod,,} m)\rightarrow a\equiv a’(\mathrm{mod,,} \frac md)}
$$

公式三证明：
$$
\because (k,m)=d,\therefore(\frac kd, \frac md)=1\
又\because m | k(a-a’)
\therefore \frac md|\frac kd(a-a’)\
又\because \frac md与\frac kd互质， \therefore \frac md | a-a’，得证
$$

公式三更一般的结论：
$$
ka\equiv ka’(\mathrm{mod,,} m)\rightarrow a\equiv a’(\mathrm{mod,,} \frac m{(m,k)})
$$

线性同余方程

$$
ax\equiv b(\mathrm{mod,,} m)\leftrightarrow ax+my=b
$$

对 $mx\equiv 0(\mathrm{mod,,}m),ax\equiv b(\mathrm{mod,,}m)$ 辗转相除

还有一种计算方法比较好理解（来自dls）
$$
\begin{cases}
100x\equiv 0(\mathrm{mod,,}100),(1)\
87x\equiv3(\mathrm{mod,,}100),(2)
\end{cases}
$$

$$
(1)-(2)得,13x\equiv97(\mathrm{mod,,}100),(3)\
(2)-6\times(-3)得,9x\equiv 21(\mathrm{mod,,}100),(4)\
(3)-(4)得,4x\equiv 76(\mathrm{mod,,}100)\
(4)-2\times(5)得，x\equiv69(\mathrm{mod,,}100)
$$

解线性同余方程板子：

1
2
3
4
5
6
7
8
9
10
// 求 a * x = b (mod m) 的解
ll modequ(ll a, ll b, ll m) {
    ll x, y;
    ll d = exgcd(a, m, x, y);
    if (b % d != 0) return -1;
    m /= d; a /= d; b /= d;
    x = x * b % m;
    if (x < 0) x += m;
    return x;
}

简化剩余系

所有的 n 满足 $0<n\leq m,(n, m)=1$ 构成了一个模 m 的简化剩余系。$\phi(m)$ 表示 n 的个数。

欧拉函数

$$
\phi(m)=m\prod_{p|m}(1-\frac1p)
$$

欧拉函数证明

$$
积性函数性质 \phi(mn)=\phi(m)\phi(n)和唯一分解定理 n=p_1^{a_1}p_2^{a_2}…p_k^{a_k}\
因此\phi(n)=\phi(p_1^{a_1})…\phi(p_k^{a_k}),\对于任意一项都有
\bbox[yellow]{\phi(p_s^{a_s})=p_s^{a_s}-p_s^{(a_s-1)},(1)}\
试证(1):从1到p_s^{a_s}共有p_s^{a_s}个数字，不互质的数有\bbox[yellow]{p_s,2p_s,…,p_s^{a_s-1}}共{p_s^{a_s-1}}项\
则互质的数有\bbox[yellow]{p_s^{a_s}-p_s^{a_s-1}}个，即\phi(p_s^{a_s})=p_s^{a_s}-p_s^{a_s-1}=p_s^{a_s}(1-\frac1{p_s})\
可以把该式子推广到质数分解的每一项因子，则有:\
\phi(n)=\phi(p_1^{a_1})…\phi(p_k^{a_k})
=p_1^{a_1}…p_k^{a_k}*(1-\frac1{p_1})…(1-\frac1{p_k})=n\prod_{i=1}^{k}(1-\frac1{p_i})
$$

欧拉函数板子

1
2
3
4
5
6
7
8
9
10
11
ll phi (ll n) {
    ll ans = n;
    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1); //*(1-1/i)
            while (n % i == 0)  n /= i;
        }
    }
    if (n > 1)  ans = ans / n * (n - 1); //还剩下就再乘
    return ans;
}

欧拉定理

==若 $(a,m)=1$,则 $a^{\phi(m)}\equiv1(\mathrm{mod,,}m)$==

m为素数时有 费马小定理：$a^{p-1}\equiv1(\mathrm{mod,,}p)$

欧拉定理证明

设 $1-n$ 中与 $n$ 互质的数为：$k_1, k_2, …, k_{\phi(n)}$，则有 $ak_1,ak_2,…ak_{\phi(n)}$，二者在模n意义下等价（可以手搓几个例子模拟），

二式分别累乘，有 $k_1k_2…k_{\phi(n)}\equiv a^{\phi(n)}k_1k_2…k_{\phi(n)} (\mathrm{mod,,}n)$，即
$$
\prod_{i=1}^{\phi(n)}k_i\equiv a^{\phi(n)}\prod_{i=1}^{\phi(n)}k_i(\mathrm{mod,,}n)
$$

根据同余公式三 $ka\equiv ka’(\mathrm{mod,,} m)\rightarrow a\equiv a’(\mathrm{mod,,} \frac m{(m,k)})$

则有
$$
\prod_{i=1}^{\phi(n)}k_i\equiv a^{\phi(n)}\prod_{i=1}^{\phi(n)}k_i(\mathrm{mod,,}n)\rightarrow
1\equiv a^{\phi(n)}(\mathrm{mod,,}n)
$$

扩展欧拉定理

$$
a^b\equiv\begin{cases}
a^{b\mathrm{,mod,}\phi(m)},& \mathrm{gcd}(a,m)=1,\
a^b,& \mathrm{gcd}(a,m)\neq 1,b<\phi(m),,,,,,,\ (\mathrm{mod,,}m)\
a^{(b\mathrm{,mod,\phi(m)}) + \phi(m)},& \mathrm{gcd}(a,m)\neq1,b\geq \phi(m).
\end{cases}
$$

$$
a^b\mathrm{mod,}m=a^{b\mathrm{,mod,}\phi(m)+\phi(m)}\mathrm{,mod,}m,,,(b\geq \phi(m))
$$
因为多次取模之后会进入一个循环

逆元

$ax\equiv1(\mathrm{mod,,}m)$，称 $x$ 为 $a$ 的逆元，记作 $a^{-1}$

快速幂求逆元模板

素数：

$a^{p-1}\equiv1(\mathrm{mod},,p)\rightarrow aa^{p-2}\equiv1(\mathrm{mod,,p)\rightarrow a^{p-2}\equiv a^{-1}(\mathrm{mod},,p})$

1
2
3
4
5
6
7
8
9
10
ll qmi(ll a, ll k, ll p) {
	ll ans = 1;
	while (k) {
		if (k & 1)	ans = ans * a % p;
		k >>= 1;
		a = a * a % p;
	}
	return ans;
}
//a mod p 的逆元为 qmi (a, p - 2, p)

扩展欧几里得求逆元模板

非素数：

$a^{\phi(m)}\equiv1(\mathrm{mod,,}m)\rightarrow a^{\phi(m)-1}\equiv a^{-1}(\mathrm{mod,,}m)$

1
2
3
int d = exgcd(a, p, x, y);
if (d == 1) 	cout << (1ll * x + p) % p << endl;
else 	puts("impossible");

线性递推求逆元（1 - n）

inv[i] = (p - p / i) * inv[p % i] % p

证明（相当于等式变形）：
$$
p= (p,,\mathrm{mod,,}i)+\lfloor\frac pi\rfloor\times i\两边同除p,得,
0\equiv ((p,,\mathrm{mod,,}i)+\lfloor\frac pi\rfloor\times i),,(\mathrm{mod,,}p)\移项+同除,得,
-\lfloor\frac pi\rfloor \equiv ((p,,\mathrm{mod,,}i)\times i^{-1}),,(\mathrm{mod,,}p)\
i^{-1}\equiv -\lfloor\frac pi\rfloor \times (p\mathrm{,,mod,,}i)^{-1},,(\mathrm{mod,,}p)\
右边就是负数取模,加上个p就得证 i^{-1}\equiv p-\lfloor\frac pi\rfloor \times (p\mathrm{,,mod,,}i)^{-1},,(\mathrm{mod,,}p)
$$
板子：

1
2
3
4
inv[1] = 1;
for (int i = 2; i <= n; i++) {
    inv[i] = (p - p / i) * inv[p % i] % p;
}

前缀乘积qiu’ni’yuan

$$
令s_i=\prod_{j=1}^ia_j,,,t_i=\prod_{j=1}^i a_j^{-1}，则有a_i^{-1}=s_{i-1},t_i
$$
然后利用 $s_1\rightarrow s_2\rightarrow…\rightarrow s_n \rightarrow t_n\rightarrow…\rightarrow t_2\rightarrow t_1$ 求出每一项 $s_i,t_i$，从而求得 $a_i$

其中， $s_n \rightarrow t_n$ 这一步可以通过 $exgcd$ 求逆元得出

==利用前缀乘积，正反正 for 三遍即得==

板子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve () {
    s[0] = 1;
    for (int i = 1; i <= n; i++)    s[i] = s[i-1] * a[i] % p;
    ll x, y;
    exgcd (s[n], p, x, y);
    if (x < 0)  x += p;
    t[n] = x;

    for (int i = n; i >= 1; i--)    t[i-1] = t[i] * a[i] % p;
    for (int i = 1; i <= n; i++) {
        ll v = s[i-1] * t[i] % p;
        ans ^= v;
    }
    cout << ans;
}

Reference

求逆元的三种方法：https://zhuanlan.zhihu.com/p/100587745

习题

欧拉函数模板题 http://oj.daimayuan.top/course/12/problem/489

求逆元1 http://oj.daimayuan.top/course/12/problem/490

求逆元2 http://oj.daimayuan.top/course/12/problem/491