0%

ProjectEuler-437

开学了~

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

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