开学了～

Problem

求 $[1, 10^8]$ 内满足存在一个原根 $g$ 且 $1 + g \equiv g^2 \mod{p}$ 的素数 $p$ 的和。

Solution

首先我们注意到 $1 + g \equiv g^2 \mod{p}$ 这个方程还是可以用普通的方法去解：

$$g \equiv \frac{1 \pm \sqrt{5}}{2} \mod{p}$$

如果 $\sqrt{5}$ 在模 $p$ 下不存在的话肯定无解。如何判断存不存在？请关注 二次剩余 以及 勒让德符号 。

然后怎么解 $\sqrt{5}$ 呢？我们有 Tonelli–Shanks Algorithm ……

对于每个质数暴力判断这两个数是否是原根就好了。

nonsense

我就不告诉你我是写了个暴力跑了 3h40min 跑出来的。

不得不吐槽上学几件事。

计算机入门！全英文授课！作业要用 LaTeX ！还要用英文！

微积分！从头开始学习一个数学系统！概念什么的给我去死吧！

抽象代数！我终于明白了 $\mathbb{Z}/n \mathbb{Z}$ 是什么意思了……那个除号就是表示 除法 商环（你可以理解为环与环之间的除法）啊！

线性代数！老师讲“交换矩阵的行和列不改变矩阵行列式”讲了 20min ……

体育！分级考试要考引体向上！只能做三个的哭了……