C++에서 주어진 범위에서 x^2 =1(mod p)의 솔루션 수 계산

정수 x와 p가 주어집니다. 목표는 방정식 -x ² 의 해의 수를 찾는 것입니다. =1 ( mod p ) x가 [1,N] 범위에 있도록

우리는 이것을 1에서 N으로 순회하고 (x*x)%p==1이면 각 숫자를 x 검사로 사용합니다. 그렇다면 카운트를 증가시키십시오.

예를 들어 이해합시다.

입력 - 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 ( 모드 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<<"Number of solutions :"<<solutionsCount(n, p);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Number of solutions : 6