Zenn
🕌

【C#アルゴリズム】合同式(Mod)とは？

2024/11/29に公開
C#
アルゴリズム
mod
tech

はじめに

paiza　でModにまつわる問題が出てきたのでこれについてまとめました。

Mod（モジュロ演算）の概要

  • モジュロ演算（mod演算）は、ある整数を別の整数で割ったときの「余り」を計算する演算です。
  • 通常、a \bmod b と書き、C#では % 演算子を使います。

例:

7 \bmod 3 = 1 \quad (\text{7 を 3 で割った余りは 1})

Modの合同

「合同」とは、2つの整数が、ある数で割ったときに同じ余りを持つことを意味します。

a と b が m に関して合同であるとは、次のように書きます：

a \equiv b \pmod{m}

例:

17 \equiv 5 \pmod{6} \quad (\text{17 も 5 も 6 で割ると余りが 5})

ちなみにこれを**mを法として合同**といいます。

Modの演算

  1. 足し算:

    (a + b) \bmod m \equiv (a \bmod m + b \bmod m) \bmod m

  2. 引き算:

    (a - b) \bmod m \equiv (a \bmod m - b \bmod m + m) \bmod m

    ※ 足し算に +m を加えることで負の余りを回避します。

  3. 掛け算:

    (a \cdot b) \bmod m \equiv (a \bmod m \cdot b \bmod m) \bmod m

  4. 累乗:

    a^n \bmod m \quad = (a \bmod m)^n \bmod m

Modの逆元

  • a の m に関する 逆元 とは、次のような整数 x のこと：
    a \cdot x \equiv 1 \pmod{m}
  • 逆元は、a と m が互いに素である場合（\text{GCD}(a, m) = 1）に存在します。（ax + my = 1の場合、変形するとax = -my + 1となるため）
  • 計算には拡張ユークリッドの互除法を使います。

C#コード例

足し算・引き算・掛け算・累乗

using System;

class Program
{
    static void Main()
    {
        int a = 7, b = 5, m = 6;

        // 足し算
        int add = (a % m + b % m) % m;
        Console.WriteLine($"(a + b) % m = {add}"); // 結果: 0

        // 引き算
        int sub = (a % m - b % m + m) % m;
        Console.WriteLine($"(a - b) % m = {sub}"); // 結果: 2

        // 掛け算
        int mul = (a % m * b % m) % m;
        Console.WriteLine($"(a * b) % m = {mul}"); // 結果: 5

        // 累乗
        int pow = ModPow(3, 4, 5); // 3^4 % 5
        Console.WriteLine($"(3^4) % 5 = {pow}"); // 結果: 1
    }

    private static int ModPow(int baseNum, int exponent, int mod)
    {
        int ans = 1;
        for (int i = 0; i < exponent; i++)
        {
          ans *= baseNum;
          ans %= mod;
        }
        return ans;
    }
}

Modの逆元

using System;

class Program
{
    static void Main()
    {
        int a = 3, m = 7;

        // 逆元計算
        int inv = ModInverse(a, m);
        Console.WriteLine($"Inverse of {a} mod {m} = {inv}"); // 結果: 5
    }

    // 拡張ユークリッドで逆元を計算
    private static int ModInverse(int a, int mod)
    {
        int x, y;
        int gcd = ExtendedGcd(a, mod, out x, out y);
        if (gcd != 1) throw new ArgumentException("逆元が存在しません");
        return (x % mod + mod) % mod;
    }

    // 拡張ユークリッドの互除法
    private static int ExtendedGcd(int a, int b, out int x, out int y)
    {
        if (b == 0)
        {
            x = 1;
            y = 0;
            return a;
        }
        int gcd = ExtendedGcd(b, a % b, out int x1, out int y1);
        x = y1;
        y = x1 - (a / b) * y1;
        return gcd;
    }
}

まとめ

  • Mod演算 は整数の剰余を計算する便利な道具。
  • 足し算、引き算、掛け算、累乗、逆元などに応用でき、競技プログラミングや暗号理論でよく使用されます。
  • 逆元や累乗では効率的なアルゴリズム（拡張ユークリッド法、繰り返し二乗法）を用いるのがポイントです。
  • 累乗計算には繰り返し二乗法を用いるとさらに最適化できます。（別記事で説明します）

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
https://amzn.to/3YtOnpz

Discussion