素数を法とする計算
加算と乗算を行い、mod の範囲内に保ちます
「素数を法とする計算」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
剰余を取る理由
コンテストの答えは、ほかの場所で使える整数型の範囲をはるかに超えるほど大きくなることがあります。そのため問題では、数を小さく保つために、大きな素数を法とする結果を求めます。🔢
有名な mod を知る
最もよく使う素数は 1000000007 で、1e9+7 と書かれることもあります。衝突を避けるには十分大きく、64ビットに収めるには十分小さい値です。
MOD = 1000000007剰余の意味
剰余演算子は、割り算の余りを返します。17 % 5 が 2 になるのは、17 を 5 で割ると余りが 2 になるためです。
print(17 % 5) # 2加算も mod の範囲に収まる
先に加算して最後に mod を取ることも、計算の途中で mod を取ることもできます。どちらでも余りは同じなので、値を小さく保つためにこまめに剰余を取りましょう。
total = (a + b) % MOD乗算も mod の範囲に収まる
乗算でも同じ規則が成り立ちます。積を素数で割った余りを取ります。Python は大きな整数を標準で扱えますが、mod を取れば各値を小さく保てるため、高速に処理できます。
prod = (a * b) % MOD各ステップの後に剰余を取る
長いループでは、反復するたびに % MOD を適用します。これにより数値が膨れ上がるのを防ぎ、各操作のコストを小さく予測しやすくできます。
ans = (ans * i) % MOD減算では負になることがある
多くの言語では減算によって負の余りが生じることがあります。最後に mod を取る前に MOD を加えて、結果が安全な 0 以上の範囲に収まるようにします。
diff = (a - b + MOD) % MODPython の扱いやすい剰余
朗報です。Python の % は、正の modulus に対して常に負でない結果を返します。そのため -1 % 7 は -1 ではなく 6 となり、補正処理が不要です。
print(-1 % 7) # 6演算に対して剰余を分配できる
基本的な考え方は、加算と乗算について (a op b) % m が (a%m op b%m) % m と等しくなることです。これにより、値を組み合わせる前に入力を小さくできます。
割り算には注意が必要
加算、減算、乗算は mod の下でそのまま扱えます。しかし通常の割り算はそうではなく、このコースの後半で扱う逆元が必要になります。
先頭で MOD を一度だけ設定する
解答の冒頭で MOD を定数として定義します。コードのあちこちに 1000000007 を書いて誤りが紛れ込むより、名前を付けた値を1つ使うほうが安全です。
MOD = 10**9 + 7確認問題
減算の mod を取る前に MOD を加えるのはなぜでしょうか。
まとめ
これで、1e9+7 のような素数を法とする剰余を使って、大きな個数を小さく保てるようになりました。加算、減算、乗算の各ステップで剰余を取り、負の値に注意し、割り算は逆元を使うまで保留しましょう。🎯
よくある質問
「素数を法とする計算」レッスンは無料ですか？
はい。「素数を法とする計算」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「素数を法とする計算」で何を学びますか？
加算と乗算を行い、mod の範囲内に保ちます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「素数を法とする計算」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。