Exponial (오일러 정리 및 지수 순환 정리 활용)
문제 링크: http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2021
설명
매우 큰 수를 좋아하는 사람들은 이 문제를 관심 있게 읽을 것입니다. 다음은 대규모 수 생성 방법의 예시입니다:
거듭제곱: 42^2016 = 42 × 42 × ... × 42 (2016번 반복)
팩토리얼: 2016! = 2016 × 2015 × ... × 2 × 1
이 문제에서는 'exponial'이라는 연산을 탐구합니다. 모든 양의 정수 n에 ...
7월 2일 05:14에 게시됨
Codeforces Round 864 (Div. 2) E. Li Hua and Array
문제 개요
배열의 각 원소에 대해 오일러 함수를 반복적으로 적용하면서, 특정 범위 내의 모든 원소가 동일한 값으로 수렴하는 최소 연산 횟수를 구하는 문제입니다. 이 과정에서 선형 시간 전처리와 세그먼트 트리, 그리고 LCA(Lowest Common Ancestor) 기법을 결합하여 효율적인 쿼리를 처리합니다.
핵심 아이디어
오일러 함수 φ(n)는 정수 n에 대해 1부터 n까지의 자 ...
6월 19일 02:59에 게시됨