[BOJ] 13358. Exponial

문제 링크

$n$과 $m$이 주어졌을 때 아래 식에서 $ans$를 구하면 되는 문제입니다.

풀이를 설명하기 전에 아래와 같이 $E_{i}$와 $\phi^{i}(n)$을 정의하겠습니다.

처음 이 문제를 볼 때 오일러의 정리를 연쇄적으로 사용해서 해결할 수 있을것 같다는 생각이 들었습니다.

실제로 다음과 같이 식을 전개할 수 있습니다.

여기서 $E_{i} \equiv k_{i} \mod \phi^{n-i}(m)$이고 $g_{i}$는 $\gcd(\frac{n-i}{g_i}, \phi^{i}(m))=1$을 성립시키는 가장 작은 양의 정수입니다. 그러면 오일러의 정리를 계속 사용할 수 있어 위와 같이 식 전개를 할 수 있습니다.

그럼 식을 어디까지 전개해야할까요? 먼저 다음 정리를 증명해 보겠습니다.

Theorem 1. $m \geq 2$이면 $\phi^2(m) \leq \frac{m}{2}$

$m = 2^{r}\displaystyle\prod_{p_i}{p_i^{r_i}}$라고 합시다.

Case 1) $r > 0$
$\phi(m) = 2^{r-1}\displaystyle\prod_{p_i}{p_i^{r_i-1}(p_i-1)} \leq \frac{1}{2}\phi(m)$가 성립합니다. $\phi^2(m) \leq \phi(m)$은 자명하므로 $\phi^2(m) \leq \frac{m}{2}$가 성립합니다.

Case 2) $r = 0$
$\phi(m) \leq m - 1$은 자명합니다. 그리고 $\phi(m) = \displaystyle\prod_{p_i}{p_i^{r_i-1}(p_i-1)}$이 성립하는데 각 $p_i - 1$은 짝수이므로 $\phi(m)$ 또한 짝수입니다. 즉, Case 1)에 의하여 $\phi^2(m) \leq \frac{1}{2}\phi(m) \leq \frac{m}{2}$이 성립합니다.

즉, Theorem 1에 의하여 $O(\log{m})$번만 전개하면 충분합니다. 그런데 문제는 $g_i^{E_{n-i-1}}$를 어떻게 계산해야 할까요? 당연하지만 $\gcd(g_i, \phi^{i}(m)) \neq 1$이므로 오일러의 정리를 그대로 사용할 수 없습니다.

하지만 다음 정리를 증명하면 오일러의 정리 비슷하게 계산할 수 있게됩니다.

Theorem 2. $a^{\phi(m)} \equiv a^{2\phi(m)} \mod m$

$m = \displaystyle\prod_{i = 1}^{v}{p_i^{r_i}}, a = \displaystyle\prod_{j = 1}^{w}{q_i^{s_i}}$이라고 하겠습니다. 그리고 $\left\{ p_1, p_2, \cdots , p_u \right\} = \left\{ q_1, q_2, \cdots , q_u \right\}, \left\{ p_{u+1}, \cdots , p_v \right\} \cap \left\{ q_{u+1}, \cdots , q_w \right\} = \varnothing$라고 하겠습니다.

Case 1) $u + 1 \leq i \leq v$

$\gcd(p_i^{r_i}, a) = 1$이므로 $a^{\phi(m)} \equiv 1 \mod{p_i^{r_i}}$이 성립합니다.

Case 2) $1 \leq i \leq u$

$p_i^{p_i^{r_i-1}(p_i-1)} \equiv 0 \mod{p_i^{r_i}}$가 성립합니다. 즉, $a^{\phi(m)} \equiv 0 \mod{p_i^{r_i}}$이 성립합니다.

Case 1, 2에 의하여 $a^{\phi(m)} \equiv a^{2\phi(m)} \mod{p_i^{r_i}}$이 항상 성립합니다. 즉, 중국인의 나머지 정리에 의하여 $a^{\phi(m)} \equiv a^{2\phi(m)} \mod m$이 성립합니다.

$E_5 > 10^9$ 입니다. 즉, $g_i^{E_{n-i-1}}$를 계산할 때 ${n-i-1} \leq 4$라면 Naive하게 계산하고 $n-i-1 \geq 5$이면 $g_i^{E_{n-i-1}} \equiv g_i^{k_{n-i-1} + \phi^{i+1}(m)} \mod{\phi^{i}(m)}$ 이므로 $g_i^{k_{n-i-1} + \phi^{i+1}(m)}$를 계산하면 됩니다.

시간복잡도는 $O(\log{m} \cdot (\log{m} + \pi(\sqrt{m})))$입니다.