2020-2021:teams:i_dont_know_png:potassium:math_theory_revision_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:i_dont_know_png:potassium:math_theory_revision_1 [2020/05/17 21:29] potassium [解法1] |
2020-2021:teams:i_dont_know_png:potassium:math_theory_revision_1 [2020/05/22 20:08] (当前版本) potassium fix typos |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| 由欧拉定理，若 $(a,n)=1$ ，则 $a^{\varphi(m)}\equiv 1\pmod m$ 。 | 由欧拉定理，若 $(a,n)=1$ ，则 $a^{\varphi(m)}\equiv 1\pmod m$ 。 | ||
| - | 类似单位复根，数 $m$ 的原根 $g\in[1,m],(g,m)=1$ 满足 $\{g,g^2,...,g^{\varphi(m)}\}$ 构成模 $m$ 的一个既约剩余系。易得，对于质数 $m$ ，这个既约剩余系的取值范围为 $[1,m-1]$ 。 | + | 类似单位复根，数 $m$ 的原根 $g\in[1,m],(g,m)=1$ 满足 $\{g,g^2,\ldots,g^{\varphi(m)}\}$ 构成模 $m$ 的一个既约剩余系。易得，对于质数 $m$ ，这个既约剩余系的取值范围为 $[1,m-1]$ 。 |
| 原根的另一个定义是， $\forall p<\varphi(m), g^{\varphi(m)}\neq 1$ ，即 $\varphi(m)$ 是最小的让 $g^d\equiv 1\pmod m$ 的正整数 $d$ 。 | 原根的另一个定义是， $\forall p<\varphi(m), g^{\varphi(m)}\neq 1$ ，即 $\varphi(m)$ 是最小的让 $g^d\equiv 1\pmod m$ 的正整数 $d$ 。 | ||
| 行 45: | 行 45: | ||
| 设 $x=iB+t$ （或者 $x=iB-t$ ，都可），其中 $B$ 为块大小，先设为 $\left\lceil\sqrt c\right\rceil$ 。 | 设 $x=iB+t$ （或者 $x=iB-t$ ，都可），其中 $B$ 为块大小，先设为 $\left\lceil\sqrt c\right\rceil$ 。 | ||
| - | 那么有 $a^{iB}\equiv b\cdot a^{-t}$ ，把右半部分预处理并扔进 map 里，从小到大枚举 $i\in[0,B]$ ，通过扩欧解出来右半边 $a^{-t}$ 应当取的值，查map判断，即可 $\mathcal{O}(\sqrt c)$ 求解。 | + | 那么有 $a^{iB}\equiv b\cdot a^{-t}$ ，把右半部分预处理并扔进 map 里，从小到大枚举 $i\in[0,B]$ ，通过扩欧解出来右半边 $a^{-t}$ 应当取的值，查map判断，即可 $O(\sqrt c)$ 求解。 |
| ====== N次剩余 ====== | ====== N次剩余 ====== | ||
| 行 51: | 行 51: | ||
| 即： $x^n\equiv a\pmod m$ ，给定 $m\in prime,n,a$ ，求出 $x$ 。 | 即： $x^n\equiv a\pmod m$ ，给定 $m\in prime,n,a$ ，求出 $x$ 。 | ||
| - | 前置芝士：扩欧，原根， $BSGS$ | + | 前置芝士：扩欧，原根， BSGS |
| 模板题：[[http://acm.hdu.edu.cn/showproblem.php?pid=3930|HDU3930 Broot]]（数据范围有误，应为 $1e12$ 。数据较弱，提供[[https://paste.ubuntu.com/p/gC2QR6tFcq/|几组稍强数据]]） | 模板题：[[http://acm.hdu.edu.cn/showproblem.php?pid=3930|HDU3930 Broot]]（数据范围有误，应为 $1e12$ 。数据较弱，提供[[https://paste.ubuntu.com/p/gC2QR6tFcq/|几组稍强数据]]） | ||
| 行 59: | 行 59: | ||
| 设 $m$ 的一个原根为 $g$ ，由于 $a,x\in[0,m-1]$ ，必有 $x=0$ 或正整数 $y$ 满足 $g^{y}=x$ ， $a=0$ 或正整数 $z$ 满足 $g^{z}=a$ 。 | 设 $m$ 的一个原根为 $g$ ，由于 $a,x\in[0,m-1]$ ，必有 $x=0$ 或正整数 $y$ 满足 $g^{y}=x$ ， $a=0$ 或正整数 $z$ 满足 $g^{z}=a$ 。 | ||
| - | 容易通过 $BSGS$ 求出 $z$ ，现在 $g^{yn}\equiv g^{z} \pmod m$ 式中只有 $y$ 未知。 | + | 容易通过 BSGS 求出 $z$ ，现在 $g^{yn}\equiv g^{z} \pmod m$ 式中只有 $y$ 未知。 |
| 式子等价于： $yn\equiv z\pmod \varphi(m)$ ，可以用扩欧求出 $y$ 的一个解 $y_0$ 。 | 式子等价于： $yn\equiv z\pmod \varphi(m)$ ，可以用扩欧求出 $y$ 的一个解 $y_0$ 。 | ||
| 行 67: | 行 67: | ||
| <hidden 解法1> | <hidden 解法1> | ||
| - | <codedoc code:c++> | + | <code:c++> |
| #include<cstdio> | #include<cstdio> | ||
| #include<algorithm> | #include<algorithm> | ||
| 行 218: | 行 218: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </codedoc> | + | </code> |
| </hidden> | </hidden> | ||
| 行 228: | 行 228: | ||
| 现在 $(g^{n})^{y}\equiv a \pmod m$ 式中只有 $y$ 未知。 | 现在 $(g^{n})^{y}\equiv a \pmod m$ 式中只有 $y$ 未知。 | ||
| - | 通过 $BSGS$ 可以求出所有符合要求的 $y$ ，但这里的 $BSGS$ 需要使用 ''%%map<int,vector>%%'' ，因为 $g^n$ 不是原根， $a^{t}$ 部分并非一对一关系。过后根据 $y$ 算出 $x$ 即可。 | + | 通过 BSGS 可以求出所有符合要求的 $y$ ，但这里的 BSGS 需要使用 ''%%map<int,vector>%%'' ，因为 $g^n$ 不是原根， $a^{t}$ 部分并非一对一关系。过后根据 $y$ 算出 $x$ 即可。 |
| 这两种解法都通过了原根进行转换，第一种方法由于没有使用较为复杂的 ''%%map%%'' ，常数比较小；第二种方法则更加简便、易写。 | 这两种解法都通过了原根进行转换，第一种方法由于没有使用较为复杂的 ''%%map%%'' ，常数比较小；第二种方法则更加简便、易写。 | ||
| 行 234: | 行 234: | ||
| <hidden 解法2> | <hidden 解法2> | ||
| - | <codedoc code:c++> | + | <code:c++> |
| #include<cstdio> | #include<cstdio> | ||
| #include<algorithm> | #include<algorithm> | ||
| 行 371: | 行 371: | ||
| return 0; | return 0; | ||
| } | } | ||
| - | </codedoc> | + | </code> |
| </hidden> | </hidden> | ||
2020-2021/teams/i_dont_know_png/potassium/math_theory_revision_1.1589722145.txt.gz · 最后更改: 2020/05/17 21:29 由 potassium
