クイズです。$p/q \equiv 714236805 \pmod{998244353}$ を満たす互いに素な整数のペア $(p, q)$ はなんでしょうか。 答えは $(113, 355)$ です*1。今日の話は、これを一般的に求める方法です。 裏話 $1/3 \equiv 332748118$ みたいなのだとパターンマッチで…

$n^2+2n+1 = (n+1)^2$ です。$n = -1$, $n = 0$ のとき $0$, $1$ であり素数ではありません。$n \ge 1$ のとき素数二つ以上の積となるので素数ではありません。 また、$n \lt -1$ についても同様に素数でないことがわかります。 よって、$n^2+2n+1$ 型の素数…

導入 rsk0315.hatenablog.com こういう話はある*1んですが、最初からバグらせやすい書き方をしておいて「バグが出たー」と言われてもそれはそうとなってしまうので、そういうのを控えるくらいのことはするべきだと思います。 書き方が悪いせいで「十分に複雑…

期間が過ぎたので公開を終了しました。

詳しく解説編があるかはわかりません。 下記のような状況に対する別の策です。 rsk0315.hatenablog.com rsk0315.hatenablog.com 導入 今回は、浮動小数点数をそもそも使わない方針で考えます。 ある（自分で決める）上限 $b$ に対して、分母が $b$ 以下の（…