ProjectEuler 437 - Fibonacci primitive roots

开学了～

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 ……

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