数论
欧拉函数
定义：$\phi(n) = \sum _{i = 1} ^n [\gcd(i, n) = 1]$
即1 ~ n 中和 n 互质的数的个数。
例如 \phi(1) = 1, \phi(20) = 8, 因为1， 3， 7， 9， 11， 13， 17， 19 与 20互质。
显然， 若 p 为质数， 则 \phi(p) = p - 1
设 n = p_1^{q_1} * p_2^{q_2} * p_3^{q_3}..., (p_1, p_2, p_3... 为 n 的质因数 )
特点：
-
- 欧拉函数是积性函数， 即如果有 \gcd(x, y) = 1, 则 f(x * y) = f(x) * f(y)
-
- p 为质数时， 对于 p^k , f(p^k) = p^k * \frac{p - 1}{p}
-
- 由特点2可推: f(n) = f(p1^{q1}) * f(p2^{q2}) ...
特点2证明: f(p ^ k) = p ^ k - p ^ {k - 1} = p^k * \frac{p - 1}{p}
欧拉函数公式： f(n) = n * \frac{p_1 - 1}{p_1} * \frac{p_2 - 1}{p_2}...
例题:洛谷UVA10179
这里不加证明的给出一个伟大的结论：任何积性函数都可以线性筛。
对于一个质数 p ,
若 a \bmod p \ne 0, 则有 \phi(a * p) = \phi(a) * \phi(p) = \phi(a) * (p - 1)
若 a \bmod p = 0 , 则有 \phi(a * p) = \phi(a) * p
由此得到线性筛求欧拉函数， 代码如下。
phi[1] = 1;
for(int i = 2;i <= 1e6 + 7;i++)
{
if(!vis[i])
{
prime[++cntp] = i;//质数存入质数表
phi[i] = i - 1;
}
for(int j = 1;prime[j] && i * prime[j] <= 1e6 + 7;j++)
{
vid[i * prime[j]] = 1;
if(i % prime[j] == 0 )//case1 倍数关系
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else //case2 互质关系
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
类似的， 我们也可以使用线性筛求逆元， 因子合数， 莫比乌斯函数.
欧拉定理: 若 \gcd(a, n) = 1, 则 a^{\phi(n)} \equiv 1(\bmod n).(当 p 为质数时， 可得费马小定理)
用途：
- 1.可用于在 p 不是质数， 但 a, p 互质的情况下求逆元。
- 2.可用于对指数取模， 降低指数规模。
a ^ b \equiv (a \bmod n)^{b \bmod \phi(n)}(\bmod n)
裴蜀定理：若 a, b 是整数， 且 $\gcd (a, b) = d$， 则对于任意的整数 x, y, ax + by 一定是 d 的倍数，特别的， 一定存在整数 x, y, 使 $ax + by = d$成立。
证明： 设 ax + by 的最小正整数值为 r ， 考虑 a \bmod r.
设 p = \lfloor \frac{a}{r} \rfloor, 则 a \bmod r = a - pr
代入 r, 得 $a - p(ax + by)$， 进一步得 a(1 - px) + b(-py),也是 ax' + by' 的形式。
考虑到 0\le a \bmod r < r, 以及 r 是 ax + by 的最小正整数值。所以 a \bmod r = 0, 即 r 是 a 的因数。
板子：洛谷P4549
扩展欧几里得算法(exgcd):
求$ax + by = gcd(a, b) 的一组解 (x, y)$
由裴蜀定理可知: bx + (a \bmod b)y = gcd(b, a\bmod b)
考虑辗转相除法， 可得以下式子:
- ax_1 + by_1 = gcd(a, b)
- bx_2 + (a \bmod b)y2 = gcd(a, b)
联立可得 ax_1 + by_1 = bx_2 + (a \bmod b)y_2
=> ax_1 + by_1 = bx_2 + (a - [a / b] * b)y_2
=> ax_1 + by_1 = ay_2 + b(x_2 - [a/b]y_2)
=> x_1 = y_2, y_1 = x_2 - [a / b]y_2.
代码实现如下:
int x, y;
void exgcd(int a, int b)
{
if(b == 0)
{
x = 1;
y = 0;
return;
}
exgcd(b, a % b);//递归
int tmp = x;
x = y;
y = tmp - (a / b) * y;//更改x, y的值.
}
在求出一组解 x0, y0 之后， 可求通解为：
x = x_0 + \frac{b}{\gcd(a, b)}t
y = y_0 - \frac{a}{\gcd(a, b)}t ( t 为参数， 且为整数)
板子:洛谷P5656
exgcd也可以用来求逆元， 有裴蜀定理可知， 若 a 和 p 互质， 则存在 ax + py = 1, 即 ax \equiv 1 (\bmod p)
求出[0, p ) 之间的 x 即为 a 在模 p 意义下的逆元。
即求出 ax + py = 1 的一组解.
中国剩余定理
问题原型：求解关于 x 的同余方程组：
- x \equiv 2 (\bmod 3)
- x \equiv 3 (\bmod 5)
- x \equiv 2 (\bmod 7)
解得最小的 x 为23.
设 M = m_1 * m_2 * ... * m_n, 再设 M_i = \frac{M}{m_i}
设 t_i 为满足线性同余方程 M_it_i \equiv 1 (\bmod m_i) 的最小整数解, t = 1, 2, 3, …n.
由证明可得 x 的通解为： x = kM + \sum_{i = 1}^{n}a_iM_it_i, k \notin \mathbb Z
小组成员：邵品渊， 邵品砚， 蒋佳成， 顾天泽， 马天翔， 陈继宇