C++で指定された範囲内のx^2 =1（mod p）の解の数を数えます

これを行うには、1からNまでトラバースし、各数値をxチェックとして（x * x）％p==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
Total number of solutions=3.

入力 − 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
Total number of solutions=2

以下のプログラムで使用されるアプローチは次のとおりです

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

• 関数solutionsCount（int n、int p）は、パラメーターnとpの両方を取り、方程式x ² の解の数を返します。 ％p ==1（またはx ² =1（mod p））。

• x=1からx=nまで、x * x ==1かどうかを確認し、はいの場合はカウントをインクリメントします。

• ループの最後に、カウントにはソリューションの数が含まれます。

• 結果としてカウントを返します。

例

#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