세그먼트 트리와 비트셋을 활용한 쿼리 문제 해결 (Codeforces Round #538 Div.2 F)
문제 개요
주어진 배열에서 구간 곱과 그 결과에 대한 오일러 피 함수 값을 계산하는 문제입니다. 핵심 아이디어는 오일러 피 함수의 성질과 300 이하의 소수가 62개뿐이라는 점을 활용하는 것입니다.
수학적 배경
구간 [l, r]의 곱을 X라고 할 때, X를 소인수분해하면 다음과 같습니다:
X = ∏ p_i^{c_i} (i = 1 to n)
오일러 피 함수는 곱셈적 함수이므로:
φ(X) = φ(∏ ...
6월 29일 00:36에 게시됨