C++で指定された範囲内の x² ≡ 1 (mod p) の解の個数を数える方法

問題の概要

整数 n と p が与えられたとき、合同式 x² ≡ 1 (mod p) を満たす x のうち、x が範囲 [1, N] に含まれるものがいくつあるかを求めるのがこの記事の目的です。

最も基本的なアプローチは、1 から N までの各整数を順番に x として調べ、「(x × x) % p == 1」が成立するかどうかを判定し、条件を満たすたびにカウントを 1 増やしていくというものです。

それでは、具体的な例を使って理解していきましょう。

入力例 1

• 入力：n = 5、p = 2

• 出力：解の個数 = 3

• 説明：範囲 1〜5 の間で各値を確認します。

12 = 1 % 2 = 1 → count = 1
22 = 4 % 2 = 0 → count = 1
32 = 9 % 2 = 1 → count = 2
42 = 16 % 2 = 0 → count = 2
52 = 25 % 2 = 1 → count = 3
解の総数 = 3

入力例 2

• 入力：n = 3、p = 4

• 出力：解の個数 = 2

• 説明：範囲 1〜3 の間で各値を確認します。

12 = 1 % 4 = 1 → count = 1
22 = 4 % 4 = 0 → count = 1
32 = 9 % 4 = 1 → count = 2
解の総数 = 2

アルゴリズムの考え方

このプログラムでは、以下の手順を採用しています。

• 2 つの変数 n と p を受け取ります。

• 関数 solutionsCount(int n, int p) は引数 n と p を受け取り、合同式 x² ≡ 1 (mod p) の解の個数を返します。

• x = 1 から x = n まで順にループし、(x * x) % p == 1 が成立する場合はカウントを 1 増やします。

• ループが終了した時点で、count には解の総数が格納されています。

• count を結果として返します。

C++ 実装例

#include<bits/stdc++.h>
using namespace std;
int solutionsCount(int n, int p){
    int count = 0;
    for (int x=1; x<=n; x++){
        if ((x*x)%p == 1)
            { ++count; }
    }
    return count;
}
int main(){
    int n = 8, p = 3;
    cout<<"Number of solutions :"<<solutionsCount(n, p);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Number of solutions : 6

補足：計算量と注意点

この手法の時間計算量は O(N) であり、N が大きくなるほど処理に時間がかかる点に注意が必要です。また、n や p が大きい場合には x * x の計算結果が int 型の上限を超えてオーバーフローする恐れがあるため、必要に応じて long long 型を使うと安全です。さらに、p が奇素数である場合、合同式 x² ≡ 1 (mod p) の解は mod p の世界では +1 と −1 の 2 つに限られるという数学的性質があるため、これを活用すればより効率的な解法を構築することも可能です。