[BOJ 23453] Dirichlet $k$-th root

굉장히 멋진 아이디어를 사용하는 문제!! 정말 멋진 문제!!

우리는 Dirichlet convolution을 modulo p에 대해서 계산한다는 것을 관찰하자. 이때 다음을 생각한다.

 

Lemma. 모든 산술 함수 $f:\{1,\cdots,n\}\rightarrow \mathbb{Z}$에 대해서 $2^{p}>n$이면 $f^{p}\equiv \epsilon \pmod{p}$이다.

Proof. 함수 $f^{p}$는 다음과 같다. 

\[f^{p}(n)=\sum_{a_{1}\cdots a_{p}=n}f(a_{1})\cdots f(a_{p})\]

이때 summation 아래의 조건을 만족하는 튜플 $(a_{1},\cdots,a_{p})$를 고려하자. 하나의 튜플을 찾았다면 permutation을 통해 다른 튜플을 찾을 수 있다는 사실을 기억하자. 이 튜플의 서로 다른 permutation의 개수는 어떤 $r_{i}$들과 $t$에 대해서 $\frac{p!}{r_{1}!r_{2}!\cdots r_{t}!}$ 이다. $r_{i}$들의 값은 한 튜플에서 서로 같은 것이 몇 개 있는지로 구분되는데 $a_{i}$들이 모두 같지 않음을 가정하면 $p|\frac{p!}{r_{1}!r_{2}!\cdots r_{t}!}$를 얻는다. 즉, 이러한 튜플을 가지고 있는 항들의 합은 모두 $0$과 합동이다. 만약 $a_{1}^{p}=n$이라면 어떨까? $a_{1}=1$이면 $n=1$이다. 이것은 자명한 결과이다. $a_{1}\ne 1$이라 가정하자. 그럼 $a_{1}\ge 2$이고 $n\ge 2^{p}$이다. 문제의 조건에 의해서 이것은 모순이다. 따라서 이러한 튜플은 $n=1$인 경우를 제외하고 존재할 수 없다. 심지어 $f^{p}(1)=1$임이 자명하므로 우리는 $f^{p}\equiv\epsilon\pmod{p}$임을 얻는다. $\blacksquare$

 

문제의 조건인 $n=10^{5}$과 $p=998,244,353$을 고려하면 위 Lemma를 적용할 수 있다. 따라서

\[g=f^{k} \implies g^{k^{-1}\pmod{p}}\equiv f\pmod{p}\]

즉, $g^{k^{-1}\pmod{p}}$를 분할 정복을 이용해 계산하기만 하면 된다.