アルゴ道場

モジュラー演算

中級

カテゴリ: arrays

概要

モジュラー演算（剰余演算）は、数学的な演算の一種で、ある数を別の数で割った余りを扱います。コンピュータサイエンスでは、整数のオーバーフロー防止、暗号化アルゴリズム、ハッシュ関数など、多くの応用があります。モジュラー演算は、(a + b) mod m = ((a mod m) + (b mod m)) mod m のような性質を持ち、大きな数値を扱う際に計算を簡略化できます。また、モジュラー逆元やモジュラー累乗などの概念を使用して、除算や累乗の計算も効率的に行えます。競技プログラミングでは、大きな数値の計算結果をモジュロで取ることが頻繁に求められるため、このパターンの理解は非常に重要です。

コードテンプレート

Java
Python
// Java code not available
Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

モジュラー演算剰余演算モジュラー逆元拡張ユークリッドフェルマーの小定理中国剰余定理合同式オーバーフロー防止暗号化

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、 双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

  • 1

    暗号化: RSA暗号などの公開鍵暗号方式でモジュラー演算を使用

  • 2

    ハッシュテーブル: ハッシュ関数でモジュロ演算を使用してインデックスを計算

  • 3

    大きな数の計算: 競技プログラミングで大きな数の計算結果をモジュロで取る

  • 4

    周期性の検出: 数列の周期性を検出するためにモジュラー演算を使用

  • 5

    合同方程式の解法: 線形合同方程式や中国剰余定理を使った問題解決

関連するパターン

binary-exponentiationnumber-theorygcd-lcm
定石一覧に戻る