정수 n과 p가 주어졌을 때, 방정식 x² ≡ 1 (mod p)을 만족하는 해의 개수를 구하는 것이 목표입니다. 단, 해 x는 [1, N] 범위 안에 있어야 합니다.
가장 직관적인 방법은 1부터 N까지 모든 수를 하나씩 확인하는 것입니다. 각 수 x에 대해 (x × x) % p == 1이 성립하는지 검사하고, 조건을 만족하면 카운트를 1씩 증가시키면 됩니다.
예제로 이해하기
입력 예시 1
입력 − n = 5, p = 2
출력 − 해의 개수: 3
설명 − 1부터 5 사이의 범위에서 다음과 같이 계산됩니다.
1² = 1 % 2 = 1 → count = 1
2² = 4 % 2 = 0 → count = 1
3² = 9 % 2 = 1 → count = 2
4² = 16 % 2 = 0 → count = 2
5² = 25 % 2 = 1 → count = 3
총 해의 개수 = 3
입력 예시 2
입력 − n = 3, p = 4
출력 − 해의 개수: 2
설명 − 1부터 3 사이의 범위에서 다음과 같이 계산됩니다.
1² = 1 % 4 = 1 → count = 1
2² = 4 % 4 = 0 → count = 1
3² = 9 % 4 = 1 → count = 2
총 해의 개수 = 2
알고리즘 접근 방법
- 두 변수 n과 p를 입력받습니다.
- solutionsCount(int n, int p) 함수는 매개변수 n과 p를 받아 방정식 x² % p == 1, 즉 x² ≡ 1 (mod p)을 만족하는 해의 개수를 반환합니다.
- x = 1부터 x = n까지 반복하면서 (x * x) % p == 1인지 확인하고, 조건이 참이면 count를 증가시킵니다.
- 루프가 종료되면 count에는 해의 총 개수가 저장되어 있습니다.
- count를 결과값으로 반환합니다.
이 방법의 시간 복잡도는 O(N)으로, 범위의 크기에 비례하여 선형적으로 증가합니다.
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<<"해의 개수 : "<<solutionsCount(n, p);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
해의 개수 : 6