개념
최대 10^6까지 될 수 있는 두 개의 수 P와 Q가 주어지며, 이 두 수는 N = P!/Q!라는 수를 형성합니다. 우리의 목표는 연산을 최대한 많이 수행하여 N을 1로 줄이는 것입니다. 각 연산에서는 N이 X로 나누어 떨어질 경우 N을 N/X로 대체할 수 있습니다. 이때 가능한 최대 연산 횟수를 구해야 합니다.
입력 및 출력 예시
예시 1
A = 7, B = 4
출력:
4
설명: N은 210이며, 소인수는 2, 3, 5, 7입니다.
예시 2
A = 3, B = 1
출력:
2
설명: N은 6이며, 소인수는 2, 3입니다.
접근 방법
먼저 P!/Q!의 인수분해 결과는 (Q + 1) × (Q + 2) × … × (P − 1) × P의 인수분해 결과와 동일하다는 점에 주목할 필요가 있습니다.
또한, N을 오직 소인수로만 나눌 때 연산 횟수가 최대가 된다는 점도 핵심입니다. 다시 말해, 중복을 포함하여 N의 소인수 개수를 세는 것이 곧 최대 연산 횟수를 구하는 문제와 같습니다.
이를 위해 2부터 1,000,000까지 모든 수에 대한 소인수 개수를 미리 계산해 둡니다. 먼저 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 각 수의 소인수를 구하며, 그 과정은 다음과 같습니다.
- 2부터 N까지의 연속된 정수 목록(2, 3, 4, …, N)을 만듭니다.
- 처음에는 p를 가장 작은 소수인 2로 설정합니다.
- p²부터 시작하여 p씩 증가시키면서, p² 이상의 모든 배수(p(p+1), p(p+2), p(p+3) 등)를 목록에서 표시합니다.
- 목록에서 p보다 크면서 아직 표시되지 않은 첫 번째 수를 찾습니다. 그런 수가 없다면 종료하고, 있다면 p를 그 수(다음 소수)로 바꾼 뒤 3번 단계부터 다시 반복합니다.
에라토스테네스의 체를 적용한 후에는 다음 점화식을 통해 각 수의 소인수 개수를 계산할 수 있습니다.
primefactors[num] = primefactors[num / primedivisor[num]] + 1
이후 소인수 개수에 대한 누적 합(prefix sum) 배열을 만들면, 구간 [P, Q]에 대한 합을 한 번의 뺄셈으로 구할 수 있어 여러 테스트 케이스도 매우 효율적으로 처리할 수 있습니다.
구현 예제
// C++ 프로그램: 가능한 최대 연산 횟수 구하기
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// 각 숫자의 소인수 개수를 저장하는 배열
int primeFactors1[N];
// 각 숫자의 소인수 개수를 구하는 함수
void findPrimeFactors(){
for (int a = 2; a < N; a++)
// a가 소수인 경우
if (primeFactors1[a] == 0)
for (int b = a; b < N; b += a)
// 이전 배수의 값에 1을 더해 저장
primeFactors1[b] = primeFactors1[b / a] + 1;
// 누적 합 배열 생성
// 여러 테스트 케이스 처리에 유용
for (int a = 1; a < N; a++)
primeFactors1[a] += primeFactors1[a - 1];
}
// 드라이버 코드
int main(){
// primeFactors1 배열 생성
findPrimeFactors();
int P = 7, Q = 4;
// 요구되는 답 출력
cout << primeFactors1[P] - primeFactors1[Q];
return 0;
}
출력 결과
4
복잡도 분석
체를 이용한 전처리 과정의 시간 복잡도는 O(N log log N)이며, 전처리가 완료된 후에는 각 질의를 O(1)에 처리할 수 있습니다. 공간 복잡도는 소인수 개수 배열을 저장하기 위해 O(N)입니다. 덕분에 P와 Q가 최대 10^6인 경우에도 빠르게 답을 구할 수 있습니다.