数论

· · 个人记录

一:模运算与同余问题

1，中国剩余定理

中国剩余定理可求解如下形式的一元线性同余方程组

\\x\equiv{a_2}\ mod\ \ {m_2}\\ ... \\ x\equiv{a_k}\ mod\ {m_k}\end{cases}

在所有的 m_i 互质的条件下，算法流程如下：

1，算出所有模数的乘积

M=\prod_{i=1}^k m_i

2,设 M_i=\frac{M}{m_i}

3,设 k_i\equiv{M_i^{-1}}\ mod\ M

则此方程组在 mod M意义下唯一解为

a\equiv{\sum_{i=1}^ka_ik_iM_i}\ \ (mod M)

证明：观察k_iMi的性质：k_iM_i\ mod\ m_i=1

且对于任意j\ne{i}，都有k_iM_i\ mod\ m_j=0

证毕

对于模数不互质的情况，扩展中国剩余定理可解。

扩展中国剩余定理

2,离散对数问题

对于形如a^b\equiv{c} \ mod \ q的同余方程式

已知 a,c,q ，求解 b。

BSGS 算法主要运用了分块的思想，它可以处理 ab ≡ c (mod\ p) 中 a 与

• 设$ b = km + i $， $m$ 是设定的一个常量，一般取 $\sqrt{q}

• 此时有 a^{km+i} ≡ c (mod\ p)，

即 a^i\equiv{c\times{a^{-km}}}(mod\ p)

• 对于 i ∈ [0, m) ，将所有的 a_i 预处理出来存到一个 map （Baby Step）

• 从小到大枚举 k ，在 map 里查找是否存在 c\times{a^{-km}}

时间复杂度 O(\sqrt{p}\ log\ p) 。

练习题： 「SDOI2011」计算器、 「SDOI2013」随机数生成器

二：数论函数

1，数论函数概况

在中学竞赛中，我们一般只研究值域在整数集上的数论函数

设f(x)是一个数论函数，且满足f(ab)=f(a)\times{f(b)}，

（a,b为任意互质的整数），则我们称f(x)是一个积性函数

常用的积性函数有：

• 1:常数函数,1(x) = 1

• ε: 元函数， ε(1) = 1, ε(x) = 0 (x > 1)

• id: 单位函数， id(x) = x

• idk: 幂函数， idk(x) = xk

• φ: 欧拉函数，函数值为小于等于 x 且与 x 互质的正整数的个数。

• µ: 莫比乌斯函数，设正整数 x 的质因子分解 x = ∏_{i-1}^kaipi，若存

在 pi ≥ 2 ，则 µ(x) = 0 ，否则 µ(x) = (−1)^k。 µ(1) = 1 。

• σk: 除数函数， σk(x) = ∑_{d|k} d^k

欧拉函数：

对于一个数 n,考虑它的每一个质因数 p_i,在

那么可得$\varphi(n)=n-\sum{n\cdot\frac{1}{p_i}}

简化一下可得：

(想要简化过程？我不会，请感性理解)

\varphi(n)=n\prod {1-\frac{1}{p_i}}

由此，我们就可以在O(\log n) 的时间复杂度内通过质因数分解求出一个数的欧拉函数值

那如果要求求出一段范围内的欧拉函数呢？

这里给出一个结论：欧拉函数是一个积性函数，(我懒得写证明)。

考虑欧拉筛的过程：对于一个数 i, 我们从小到大枚举当前已得到的 p_j，把 i\cdot{p_j}给筛掉，直到 p_j|i为止

假设我们已经知道 \varphi(i)的值，依次从小到大枚举 p_j,

当 p_j不整除于i 时，根据积性函数的性质可得：

\varphi(i\cdot{p_j})=\varphi(i)\cdot{(p_j-1)}

否则，设i=i_0\cdot{p^k}，

=\varphi(i_0)\cdot{p^k\cdot{(1-\frac{1}{p})} \cdot{p_j}} =\varphi(i_0)\cdot{\varphi(p^k)\cdotp_j} =\varphi(i)\cdot{p_j}

至此，我们得到了欧拉函数的递推式，配合欧拉筛，我们就可以在