소인수 개수의 최대공약수 계산: 누적합과 펜윅 트리 적용
문제 분석 및 접근
주어진 데이터 크기를 고려하면 사전에 연산을 수행하는 전처리 과정이 필수적이며, 각 질의는 O(log N) 이하의 시간 복잡도로 처리해야 합니다. 함수 F(x)를 x의 서로 다른 소인수의 개수라고 할 때, 입력의 최댓값이 1,000,000이므로 1 ≤ F(x) ≤ 7의 범위를 가짐을 수학적으로 유도할 수 있습니다. 따라서 임의의 구간 [L, R]에 대해 F(x) 값이 1부터 ...
8월 24일 04:46에 게시됨
알고리즘 문제 해결: 서브태스크별 맞춤 전략
모듈러 거듭제곱 (Subtask 1-5)
첫 번째부터 다섯 번째 서브태스크는 주어진 모듈러 값 \(P\)에 대해 \(19^x \pmod P\)를 계산하는 문제입니다. 각 서브태스크별로 \(P\) 값의 특성이 달라지며, 이에 따라 접근 방식이 변화합니다.
Subtask 1-3: \(P=998244353\) 고정
이 서브태스크는 \(P=998244353\)로 고정된 경우입니다. 지수 \(x\)의 크기가 매우 클 수 있으므로, 페 ...
7월 18일 19:18에 게시됨