逆元と剰余演算 | なかけんの競プロノート
$p$ を素数とする。整数 $a$ が $p$ と互いに素なら、次が成り立つ。\\[ a^{p-1} \\equiv 1 \\pmod p \\] この式を変形すると、\[ a\cdot a^{p-2} \equiv 1 \pmod p \]となります。これは、 $\bmod p$ の世界では、 $a$ と $a^{p-2}$ を掛けると $1$ になる、ということです。 一般に、 $a$ にある値を掛けて $1$ になるとき、その値のことを $a$ の逆元(inverse element) といいます。逆数と似ていますが、逆数は数の掛け算での話をしているのに対し、逆元は $\bmod$ の世界も含めた、もっと広い世界での話をしています。逆元は、逆数を一般化したもの、ということもできます。 逆元と剰余演算の具体例 さて、ここからは具体的にコードを書いてみます。まず、次の問題を見てみましょう
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
nico_shindannin（診断人） on Twitter: "「3x-5y=1 (x,yは整数）となるx,yを1つ求めるのに、拡張ユークリッドの互除法使ったら、入力が(3,-5)で片方負だし、C++のmod演算子微妙だし、ライブラリするのやっかいじゃね？」と考えていたのじゃ…。"
