在C ++中给定范围内x ^ 2 = 1（mod p）的解的计数

给定整数x和p。目的是找到等式-x ² = 1（mod p）的解数，以使x处于[1，N]范围内。

我们将通过从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

以下程序中使用的方法如下

• 我们取两个变量n和p。

• 函数solutionsCount（int n，int p）接受参数n和p并返回方程式的解数：x ²％p == 1（或x ² = 1（mod p））。

• 从x = 1到x = n，检查x * x == 1，如果是，则递增计数。

• 在循环结束时，count将具有解决方案的数量。

• 返回计数作为结果。

示例

#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<<"解决方案数："<<solutionsCount(n, p);
   return 0;
}

输出结果

如果我们运行上面的代码，它将生成以下输出-

解决方案数： 6