개요
등차수열(Arithmetic Progression)의 첫째 항 A, 공차 d, 그리고 소수 P가 주어졌을 때, 이 수열에서 처음으로 P의 배수가 되는 항의 위치를 구하는 것이 이 글의 목표입니다. 모든 항을 하나씩 검사하는 대신, 모듈러 연산과 모듈러 역원을 활용하면 로그 시간 안에 답을 구할 수 있습니다.
입력 예시
A = 3, d = 4, P = 5
출력 예시
3
결과 설명
주어진 등차수열은 3, 7, 11, 15, …처럼 진행되며, 네 번째 항인 15가 처음으로 소수 5의 배수가 됩니다. 프로그램은 인덱스를 0부터 세므로 결과로 3을 출력합니다.
- 첫째 항 = 3
- 둘째 항 = 3 + 4 = 7
- 셋째 항 = 3 + 2 × 4 = 11
- 넷째 항 = 3 + 3 × 4 = 15 ← 최초의 5의 배수
풀이 접근법
N번째 항을 AN이라고 하면 다음과 같이 표현할 수 있습니다.
AN = A + (N − 1) × d
AN이 P의 배수라는 조건이 주어졌으므로, 적절한 상수 l에 대해 다음 식이 성립합니다.
A + (N − 1) × d = l × P
먼저 A를 A % P로, d를 d % P로 치환하면 A는 항상 P보다 작은 값이 되고, 위 식은 (N − 1) × d = l × P − A 형태로 정리됩니다.
식 정리하기
우변에 P를 더했다가 다시 빼면 다음을 얻습니다.
(N − 1) × d = P(l − 1) + (P − A)
여기서 P − A는 음수가 아닙니다. A가 이미 P보다 작은 A % P로 치환되었기 때문입니다. 양변에 mod P를 취하면 P(l − 1) 항은 사라지고 다음과 같이 단순해집니다.
((N − 1) × d) % P = (P − A) % P, 즉 ((N − 1) × d) % P = P − A
모듈러 역원(Modular Inverse) 활용
d × Y ≡ 1 (mod P)를 만족하는 Y(P보다 작은 값)를 P에 대한 d의 모듈러 역원이라고 합니다. P가 소수이므로 페르마의 소정리(Fermat's Little Theorem)에 의해 Y = d^(P−2) mod P로 계산할 수 있으며, 거듭제곱을 분할 정복 방식으로 처리하면 O(log P) 시간에 구해집니다.
양변에 Y를 곱해 정리하면 최종 답은 다음과 같습니다.
N = ((Y × (P − A)) % P) + 1
참고로 아래 구현에서는 인덱스를 0부터 세는 기준으로 ((Y × (P − A)) % P) 값을 그대로 반환합니다.
C++ 구현 예시
#include <bits/stdc++.h>
using namespace std;
// 반복 방식으로 (x^y) % p를 O(log y) 시간에 계산하는 함수
int power(int x1, int y1, int p1){
// 결과값 초기화
int res1 = 1;
// x가 p 이상이면 먼저 나머지 연산으로 줄임
x1 = x1 % p1;
while (y1 > 0) {
// y1이 홀수이면 결과에 x1을 곱함
if (y1 & 1)
res1 = (res1 * x1) % p1;
// 이 시점에서 y1은 반드시 짝수
y1 = y1 >> 1; // y1 = y1 / 2
x1 = (x1 * x1) % p1;
}
return res1;
}
// P의 배수가 되는 첫 번째 항의 인덱스를 찾는 함수
int NearestElement1(int A, int d, int P){
// 기본 조건 처리
if (A == 0)
return 0; // 첫 항 자체가 이미 P의 배수
else if (d == 0)
return -1; // 공차가 0이면 해가 존재하지 않음
else {
int Y = power(d, P - 2, P); // 페르마의 소정리로 d의 모듈러 역원 계산
return (Y * (P - A)) % P;
}
}
// 드라이버 코드
int main(){
int A = 3, d = 4, P = 5;
// A와 d를 P로 나눈 나머지로 변환
A %= P;
d %= P;
// 함수 호출 및 결과 출력
cout << NearestElement1(A, d, P);
return 0;
}
실행 결과
3
복잡도 분석
시간 복잡도: O(log P) — 모듈러 역원을 거듭제곱 기반으로 계산하는 과정이 전체 비용을 지배합니다.
공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.