BOJ 30913 - 위수는 쿼리입니까?
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 1024 MB |
문제
$2$ 이상의 자연수 $N$과, $1$ 이상 $N-1$ 이하의 자연수 $a$에 대하여 $a^e\equiv 1\pmod{N}$을 만족시키는 가장 작은 $1$ 이상의 정수 $e$를 법 $N$에 대한 $a$의 위수(order)라고 하고, $\operatorname{ord}_N(a)$로 표기합니다. 만약 그러한 수 $e$가 존재하지 않는 경우 편의상 $\operatorname{ord}_N(a) = 0$으로 정의합니다.
자연수 $N$이 주어졌을 때, 다음과 같은 쿼리를 처리해봅시다.
- 1 $a$: $\operatorname{ord}_N(a)$를 출력합니다. ($1\leq a\leq N-1$)
- 2 $e$: $\operatorname{ord}_N(a) =e$를 만족시키는 $1$ 이상 $N-1$ 이하의 자연수 $a$를 아무거나 하나 출력합니다. 만약 그러한 수가 존재하지 않으면 0을 출력합니다. ($1\leq e\leq N-1$)
- 3 $e$: $\operatorname{ord}_N(a) =e$를 만족시키는 $1$ 이상 $N-1$ 이하의 자연수 $a$의 개수를 출력합니다. ($1\leq e\leq N-1$)
- 4 $e$: $\operatorname{ord}_N(a) =e$를 만족시키는 $1$ 이상 $N-1$ 이하의 자연수 $a$의 합을 $N$으로 나눈 나머지를 출력합니다. ($1\leq e\leq N-1$)
입력
첫째 줄에 자연수 $N$이 주어집니다. ($2\leq N\leq 4\times 10^{18}$)
둘째 줄에 쿼리의 개수 $Q$가 주어집니다. ($1\leq Q\leq 10\, 000$)
다음 $Q$개의 줄에는 쿼리가 한 줄에 하나씩 주어집니다.
출력
$Q$개의 줄에 각 쿼리의 결과를 출력합니다. $\newcommand{\Bbb}[1]{\mathbb{#1}} \newcommand{\ZnZ}[1][n]{\Bbb{Z}/{#1}\Bbb{Z}} \newcommand{\ord}{\operatorname{ord}}$
풀이 과정
기본적으로 $(\ZnZ)^\times$(= $\ZnZ$의 곱셈군)의 구조를 알아야 쉽게 접근할 수 있는 문제이다. 어려운 말을 쓰자면, $(\ZnZ)^\times$는 유한 아벨군(가환군)이므로 유한 생성 아벨군의 기본 정리에 의해 순환군들로 분해되며, 중국인의 나머지 정리는 그 자세한 분해를 알려준다. (이 글에서 직접적으로 유한 생성 아벨군의 기본 정리를 사용하지는 않으며, 참고용으로만 인용했다.)
Theorem 1. (곱셈군에서 중국인의 나머지 정리) $n = p_1^{e_1}p_2^{e_2} \cdots p_r^{e_r}$로 소인수분해될 때
\[(\ZnZ)^\times \cong \prod_{i=1}^r (\ZnZ[p_i^{e_i}])^\times\]이다.
Proof. 증명을 위해 map $f : (\ZnZ)^\times \rightarrow \prod_{i=1}^r (\ZnZ[p_i^{e_i}])^\times, x \mapsto (x \bmod p_1^{e_1}, \cdots, x \bmod p_r^{e_r})$가 isomorphism임을 보이자.
먼저 $xy \bmod p^e = (x \bmod p^e)(y \bmod p^e) \bmod p^e$이므로 $f(xy) = f(x)f(y)$임을 정의로부터 쉽게 보일 수 있다. 따라서 $f$는 homomorphism이다.
다음으로 $q_i := \dfrac{n}{p_i^{e_i}} = \left(\displaystyle\prod_{j=1}^{i-1} p_j^{e_j}\right) \left(\displaystyle\prod_{j=i+1}^{r} p_j^{e_j}\right)$을 정의하자. 또 $q_i \bar q_i \equiv 1 \pmod {p_i^{e_i}}$를 만족하는 $\bar q_i$를 생각하자. 이때 $q_i$는 $p_i^{e_i}$와 서로소이므로 곱셈 역원이 항상 존재한다.
이제 $f$의 역사상을 $f^{-1} : (x_1, x_2, \cdots, x_r) \mapsto \displaystyle\sum_{i=1}^{r} x_i q_i \bar q_i$로 정의하자. $\vert(\ZnZ)^\times\vert = \vert\prod_{i=1}^r (\ZnZ[p_i^{e_i}])^\times\vert = \phi(n)$이므로 $f$가 injective나 surjective 중 하나임을 보이면 충분하다.
\[\begin{aligned} f(f^{-1}(x_1, x_2, \cdots, x_r)) & = f\bigg(\sum_{i=1}^r x_i q_i \bar q_i\bigg) \\ & = (x_1 q_1 \bar q_1 \bmod {p_1^{e_1}}, \cdots, x_r q_r \bar q_r \bmod {p_r^{e_r}}) \\ & = (x_1 \bmod {p_1^{e_1}}, \cdots, x_r \bmod {p_r^{e_r}}) \end{aligned}\]가 성립함을 보일 수 있다. 이로써 $f$는 surjective이고 따라서 isomorphism임을 보였다.
$\ZnZ[p^e]$ 역시 유한 아벨군이므로 순환군들로 분해된다. 잘 알려진 사실로,
- $p > 2$ 또는 $e < 3$인 경우 $\ZnZ[p^e]$ 자체가 순환군이다(원시근을 가진다).
- $p = 2$, $e \geq 3$인 경우 $\ZnZ[2^e]$는 순환군이 아니며, $\ZnZ[2^e] \cong \ZnZ[2] \times \ZnZ[2^{e-2}]$이다.
이를 증명하기 위해 다음 정리가 필요하다.
Theorem 2. (라그랑주 정리) 소수 $p$와 $\ZnZ[p]$ 위의 0이 아닌 다항식 $f$에 대해 $f(x) \equiv 0$의 해의 개수는 최대 $\deg f$개이다.
Proof. 수학적 귀납법을 사용한다. $\deg f = 1$인 경우, $a_1 x + a_0 \equiv 0$의 해는 $-\bar a_1 a_0$으로 유일하다. $k < n$에 대해 $\deg f = k$이 성립한다 하자. $f$의 해가 존재하지 않는다면 $0 \leq n$이므로 가정이 성립한다. 그렇지 않다면, $f$의 어떤 해를 $\alpha$라고 두자. 다항식의 나눗셈을 통해 $f$를 $\alpha$로 나눈 나머지를 $r$이라고 하면,
\[f(x) = (x-\alpha)g(x) + r\]이 성립한다. 이때 $x = \alpha$를 대입하면 $r = 0$이 되기에 $f(x) = (x-\alpha)g(x)$가 된다. 따라서 $f(x) \equiv 0 \Longleftrightarrow x-\alpha \equiv 0 \text{ or } g(x) \equiv 0$이고, $\deg g < n$이므로 $g(x) \equiv 0$의 해는 $n-1$개 이하이고, $f(x) \equiv 0$의 해는 $n$개 이하이다. 따라서 가정이 성립한다.
$p$가 소수가 아니라면 가정이 성립하지 않는 것에 주의하자. 예를 들어, $x^2 - 4 \equiv 0 \pmod{15}$는 해가 $x = 2, 7, 8, 13$으로 4개이다.
Theorem 3. 소수 $p$에 대해 $\ord_p x = d$를 만족하는 $x$의 개수를 $\psi(d)$라고 할 때,
\[\psi(d) = \begin{cases} \phi(d) & \text{if } d \mid (p-1) \\ 0 & \text {if } d \nmid (p-1) \end{cases}\]이다.
Lemma 3.1. $\ord_n x = d$인 $x$에 대해, $\ord_n (x^l) = d/{\rm gcd}(d, l)$이다.
Proof. $\small l/{\rm gcd}(d, l)$가 정수이므로 $\small (x^l)^{d/{\rm gcd}(d, l)} = x^{l \cdot d/{\rm gcd}(d, l)} = (x^d)^{(l/{\rm gcd}(d, l))} = 1 \Rightarrow \ord_n (x^l) \mid d/{\rm gcd}(d,l)$
$\small(x^l)^{\ord_n (x^l)} = x^{l \cdot \ord_n (x^l)} = 1$이므로 $\small d \mid l \cdot \ord_n (x^l)$. 양변을 $\small\gcd(d,l)$로 나누면 $\small d/{\rm gcd}(d,l) \mid l/{\rm gcd}(d,l) \cdot \ord_n(x^l)$이고, $\small d/{\rm gcd}(d, l), l/{\rm gcd}(d, l)$은 서로소이므로 $\small d/{\rm gcd}(d,l) \mid \ord_n (x^l)$.
Lemma 3.2. $x^k \equiv 1$, $x^l \equiv 1$이면 $x^{\gcd(k, l)} \equiv 1$이다. 따라서 $x^k \equiv 1$이라면 $(\ord_n x) \mid k$이다.
Proof. $\small \exists s, t \in \mathbb{Z}$ s.t. $ks+tl = \gcd(k, l)$이므로 $\small (x^k)^s \cdot (x^l)^t = x^{ks+tl} = x^{\gcd(k, l)} \equiv 1$.
더 엄밀한 증명을 위해서는 $\small s, t$가 음수일 경우, $\small x^{-k} \equiv \bar x^k$, 를 보일 필요가 있지만, 여기서는 간단히 설명하고 넘어간다.
Proof. 만약 $\ord_p x = d$인 $x$가 존재하지 않는다면, $\psi(d) = 0$이다. 그렇지 않다면, 임의의 $\ord_p x = d$인 $x$에 대해 \(S_n = \{x^0, x^1, \cdots, x^{d-1}\}\)을 생각하자. $S_n$의 모든 원소는 $x^d \equiv 1$을 만족하고 $\vert S_n \vert = d$이므로, 라그랑주 정리에 의해 $S_n$은 $x^d \equiv 1$의 해집합과 동일하다. 이제 $S_n$의 원소 중에 위수가 정확히 $d$인 것을 찾아야 한다. 이는 $0, \cdots, d-1$ 중에 $\gcd(d, l) = 1$인 $l$의 개수와 동일하고, 이는 $\phi(d)$와 같다. 따라서 위수가 $d$인 원소가 하나라도 존재한다면 $\psi(d) = \phi(d)$이다.
페르마의 소정리에 의해 모든 $x \not\equiv 0$은 $x^{p-1} \equiv 1$을 만족한다. 따라서 $\ord_p x = d$라면 $d \mid (p-1)$이 성립한다. 결과적으로 $d \nmid (p-1)$이라면 $\psi(d) = 0$임을 알 수 있다. 또한 모든 $x \not\equiv 0$은 1 이상의 위수를 가지기에,
\[\sum_{d \mid (p-1)} \psi(d) = p-1\]을 만족한다는 것을 알 수 있다. 이때 뫼비우스 반전 공식을 이용하면
\[\sum_{d \mid (p-1)} \phi(d) = p-1\]역시 보일 수 있다. 이제 두 식을 서로 빼면,
\[\sum_{d \mid (p-1)} (\phi(d)-\psi(d)) = 0\]이 된다. 이때 $\phi(d) - \psi(d)$가 $0$ 또는 $\phi(d)$라는 걸 위에서 보였고, 우변이 $0$이 되므로 $\phi(d) - \psi(d)$는 항상 $0$이 된다. 따라서 $d \mid (p-1)$이라면 $\psi(d) = \phi(d)$가 된다.
Theorem 4. ($(\ZnZ[p^e])^{\times}$에서의 원시근의 존재성) 소수 $p$와 양의 정수 $e$에 대해, $(\ZnZ[p^e])^\times$는,
- $p > 2$ 또는 $e < 3$이면 원시근을 가진다.
- $p = 2$, $e \geq 3$이면 원시근을 가지지 않으며, 대신 모든 원소를 $\pm 5^k$ 꼴로 나타낼 수 있다.
Proof.
$e = 1$의 경우
원시근의 위수는 $p-1$이고, Theorem 3에 의해 $\psi(p-1) = \phi(p-1) \neq 0$이므로 $\ZnZ[p]$는 항상 원시근을 가진다는 것을 알 수 있다.$p > 2, e \geq 2$의 경우
$(1+sp)^{p^{e-1}} = \sum_{i=0}^{p^{e-1}} \binom{p^{e-1}}{i} (sp)^{i} = 1 + sp^{e} + s^2 \frac{p^{e-1}-1}{2} p^{e+1} + \cdots \equiv 1 \pmod{p^e}$이다.
$(1+sp)^{p^{e-2}} = \sum_{i=0}^{p^{e-2}} \binom{p^{e-2}}{i} (sp)^{i} = 1 + sp^{e-1} + s^2 \frac{p^{e-2}-1}{2} p^e + \cdots \equiv 1 + sp^{e-1} \pmod{p^e}$이다.
따라서 $p \nmid s$라면 $\ord_{p^e}(1+sp) = p^{e-1}$이다.
$g$가 $(\ZnZ[p])^\times$의 원시근이라면, $g^{p-1} \equiv 1 \pmod{p}$이므로 $g^{p-1} = 1 + sp$ 꼴로 나타낼 수 있다. 만약 $p \mid s$라면, \(\begin{aligned} \quad (g+p)^{p-1} & = \sum_{i=0}^{p-1} \binom{p-1}{i} g^{p-1-i} p^{i} = g^{p-1} + (p-1)g^{p-2} p + \cdots \\ & = 1+sp + (p-1)g^{p-2}p + \cdots = 1 + (p-1)g^{p-2}p + \Big(\frac{s}{p}+\cdots\Big)p^2 \end{aligned}\)
를 대신 사용하는 것으로 $p \nmid s$로 만들 수 있다. ($\because p \nmid g^{p-2}$) 따라서 이 경우에는 $g := g+p$로 생각하자.
이제 $g^{(p-1)p^{e-2}} \equiv (g^{p-1})^{p^{e-2}} \equiv (1+sp)^{p^{e-2}} \equiv 1+sp^{e-1}\not\equiv 1$이므로 $\ord_{p^e} g \nmid (p-1)p^{e-2}$이다. 또한 $g^{\phi(p^e)} \equiv g^{(p-1)p^{e-1}} \equiv 1$이므로 $\ord_{p^e} g \mid (p-1)p^{e-1}$이다. $p$가 소수이므로 $\ord_{p^e} g = (p-1)p^{e-1}$이고, 따라서 $g$는 $(\ZnZ[p^e])^{\times}$의 원시근이 된다.$p = 2, e = 2$의 경우 ($n = 4$)
$3^0 = 1$, $3^1 = 3$이므로 $g = 3$이 원시근이 된다.$p = 2, e \geq 3$의 경우
$(1+4)^{2^{e-2}} = \sum_{i=0}^{2^{e-2}} \binom{2^{e-2}}{i} (2^2)^i = 1 + 2^{e} + 2^{e+1} (2^{e-2}-1) + \cdots \equiv 1 \pmod{2^e}$이다.
$(1+4)^{2^{e-3}} = \sum_{i=0}^{2^{e-3}} \binom{2^{e-3}}{i} (2^2)^i = 1 + 2^{e-1} + 2^{e} (2^{e-3}-1) + \cdots \equiv 1 + 2^{e-1} \pmod{2^e}$이다.
$\phi(2^e) = 2^{e-1}$이므로 $\ord_{2^e}(5) \mid 2^{e-1}$이고, 위 식에 의해 $\ord_{2^e}(5) = 2^{e-2}$라는 것을 알 수 있다. 따라서 $5$는 $(\ZnZ[2^e])^\times$의 원시근이 아니다.
$a \equiv 1 \pmod{4}$에 대해 $a \equiv 5^k \pmod{2^{e-1}}$라고 하자. 따라서 $a \equiv 5^k + b2^{e-1} \pmod{2^e}$이 \(b \in \{0, 1\}\)에 대해 성립한다. 만약 $b = 0$이라면 $\ZnZ[2^e]$에서도 $a$를 $5^k$꼴로 나타낼 수 있다. 아니라면, $5^{2^{e-3}} \equiv 1+2^{e-1} \pmod {2^e}$이므로
\(\qquad\begin{aligned} 5^{k + 2^{e-3}} & \equiv 5^k \cdot 5^{2^{e-3}} \equiv 5^k(1+2^{e-1}) \equiv 5^k + (1+4)^k(2^{e-1}) \\ & \equiv 5^k + (1+4m)(2^{e-1}) \equiv 5^k + 2^{e-1} + m \cdot 2^{e+1} \\ & \equiv 5^k + 2^{e-1} \equiv a \pmod{2^e}\end{aligned}\)
가 성립한다. 또한 $e = 3$에 대해, $1 \equiv 5^0 \pmod{2^3}$ / $5 \equiv 5^1 \pmod{2^3}$이 성립한다.
한편, $a \equiv 3 \pmod{4}$라면 $-a \equiv 1 \pmod{4}$이다. 결과적으로, $e \geq 3$와 $a \in (\ZnZ[2^e])^\times$에 대해 $a \equiv (-1)^t 5^u \pmod{2^e}$를 만족하는 정수 \(t \in \{0, 1\}, u \in \{0, \cdots, 2^{e-2}-1\}\)가 존재한다.
따라서 원시근이 존재하는 경우 $(\ZnZ[p^e])^\times \cong \ZnZ[\phi(p^e)] = \ZnZ[(p-1)p^{e-1}]$이며, $p = 2, e \geq 3$인 경우는 $(\ZnZ[2^e])^\times \cong \ZnZ[2] \times \ZnZ[2^{e-2}]$이 된다.
Theorem 5. (카마이클 $\lambda$ 함수) 다음과 같은 함수 $\lambda(n)$을 생각하자.
\[\lambda(n) = \begin{cases} \phi(n) & \text{ if $(\ZnZ[n])^{\times}$ is cyclic } (n = 1, 2, 4, p^k) \\ \frac{1}{2}\phi(n) & \text{ if } n = 2^e, e \geq 3 \\ \overset{r}{\underset{i=1}{\rm lcm}}\ \lambda(p_i^{e_i}) & \text{ if } n = p_1^{e_1} \cdots p_r^{e_r} \text{ (prime factorization)} \end{cases}\]이러한 $\lambda(n)$은 $(\ZnZ[n])^\times$에서 위수가 가장 큰 원소의 위수이다. 즉, \(\lambda(n) = \operatorname{max} \{\ord_n x : x \in (\ZnZ[n])^\times \}\)이다.
Proof. $\ZnZ[p^e]$가 원시근을 가진다면 원시근의 위수가 최대이므로 $\lambda(p^e) = \phi(p^e)$로 둘 수 있다. 원시근을 가지지 않는다면 ($p = 2, e \geq 3$) 5의 위수가 $2^{e-2} = \phi(2^e)/2$로 최대이므로 $\lambda(2^e) = \phi(2^e)/2$로 둘 수 있다. 이때 $\ZnZ[2^e]$의 모든 원소의 위수에 대해 $\ord_{2^e} x \mid \phi(2^{e}) = 2^{e-1}$임에 주목하자. 위수가 $2^{e-1}$인 원소가 존재하지는 않지만, $d \mid 2^{e-1}$, $d < 2^{e-1}$이라면 $d \mid 2^{e-2}$이므로 모든 원소의 위수는 $2^{e-2}$의 약수이다.
$n = p_1^{e_1} \cdots p_r^{e_r}$에 대해 $(\ZnZ[n])^\times$의 한 원소 $x$를 생각하자. $\ord_n x = d$라는 것은 $d$가 $x^d \equiv 1 \pmod{n}$을 만족시키는 최소의 양의 정수라는 것이다. 이때 중국인의 나머지 정리에 의해, $x^d \equiv 1 \pmod{n}$은 $x^d \equiv 1 \pmod{p_1^{e_1}, p_2^{e_2}, \cdots, p_r^{e_r}}$이라는 것과 동치이다. 따라서 $\ord_{p_1^{e_1}} \mid d, \cdots, \ord_{p_r^{e_r}} \mid d$가 성립해야 한다. 이때 $d$는 그러한 최소의 정수이므로 $d = \operatorname{lcm}\big( \ord_{p_1^{e_1}} x, \cdots, \ord_{p_r^{e_r}} x \big)$가 되어야 한다. 이제 각 $\ZnZ[p_i^{e_i}]$에 대해 원시근을 가진다면 원시근 $g_i$를, 가지지 않는다면 $g_i = 5$로 두자. 중국인의 나머지 정리에 의해 $x \equiv g_i \pmod{p_i^{e_i}}$인 $x \in (\ZnZ[n])^\times$가 존재하며, 이 원소의 위수는 $\operatorname{lcm}\big(\lambda(p_1^{e_1}), \cdots, \lambda(p_r^{e_r}) \big)$가 된다. 따라서 $\lambda(n) = \ord_n x$이다.
Theorem 6. $\forall x \in (\ZnZ[n])^\times$에 대해 $\ord_n(x) \mid \lambda(n)$이다.
Lemma 6.1. 서로소인 두 $k, l$에 대해 $\ord_n x = k$, $\ord_n y = l$이라 하자. 이때, $\ord_n xy = kl$이 성립한다.
Proof. $\small \ord_n xy = d$라고 하자. 먼저 $\small (xy)^{kl} \equiv (x^k)^l (y^l)^k \equiv 1$이 성립하므로 $\small \ord_n xy = d \mid kl$이다.
$\small (xy)^d \equiv 1$이므로 $\small x^d \equiv y^{-d}$가 성립한다. 양변에 $\small l$제곱을 하면 $\small x^{ld} \equiv y^{-ld} \equiv (y^l)^{-d} \equiv 1$이다. 따라서 $\small \ord_n x = k \mid ld$이고, $\small \gcd(k, l) = 1$이므로 $\small k \mid d$이다. 비슷하게 $\small y^{kd} \equiv 1$이므로 $\small l \mid d$이다. $k\small $와 $\small l$이 서로소이므로 $\small kl \mid d$이고, 따라서 $\small kl = d$가 된다.
Proof. 어떤 $x$에 대해 $\ord_n x = k \nmid \lambda(n)$라고 하자. 또 위수가 $\lambda(n) = d$인 원소를 $y$라고 하자. $p \mid \ord_n x$ 또는 $p \mid \ord_n y$인 모든 $p$에 대해, $g_p$를 다음과 같이 정의하자.
\[\begin{aligned} \text{Set } e_1 := \nu_p(k), e_2 = \nu_p(d) \\ g_p = \begin{cases} x^{k/p^{e_1}} & \text{if } e_1 > e_2 \\ y^{d/p^{e_2}} & \text{otherwise} \end{cases} \end{aligned}\]$\gcd(k, k/p^{e_1}) = k/p^{e_1}$이므로 $\ord_n (x^{k/p^{e_1}}) = \dfrac{k}{\gcd(k, k/p^{e_1})} = p^{e_1}$이다. 비슷하게 $\ord_n (y^{d/p^{e_2}}) = p^{e_2}$이다. 이제 $p \mid k\text{ or } p \mid d$에 대해 $g := \prod g_p$를 구하자. 각각의 $g_p$의 위수가 서로소고, 각각의 소인수 지수에 대해 최댓값을 골라 곱했으므로 $\ord_n g = \operatorname{lcm}(k, d)$이다. $k \nmid d$이므로 $\operatorname{lcm}(k, d) > d$이고, 따라서 $d = \lambda(n)$이 위수의 최댓값이라는 가정에 위배된다. 그러므로 $k = \ord_n x > \lambda(n)$인 $x$는 존재하지 않는다.
이제 문제를 풀기 위한 배경지식을 충분히 갖추었다! 쿼리들을 처리해 보자.
1번 쿼리
단순히 $a$의 위수를 출력하면 되는 쿼리이다. 우리가 사용할 것은 $\ord_N a = d$일 때 $\ord_N (a^l) = d/{\rm gcd}(d, l)$이라는 것이다. 이미 $\ord_N a \mid \phi(N)$인 것을 알고 있기에, $p \mid d$라면 $p \mid \phi(N)$임도 알 수 있다. 따라서 $p \mid \phi(N)$에 대해 $\nu_p(d)$(= $d$가 $p$를 몇 개나 인수로 가지는지)를 찾은 후 전부 곱하여 $d$를 구할 수 있다.
$d \mid \phi(N)/p^e$이고 $d \nmid \phi(N)/p^{e+1}$인 $e$를 구했다 하자. 우리는 이미 $\nu_p(\phi(N))$(= $\phi(N)$이 $p$를 몇 개 인수로 가지는지)을 알고 있으므로, $\nu_p(d) = \nu_p(\phi(N))-e$라는 것 역시 알 수 있다.
$d \mid \phi(N)/p^e$라면 $\gcd(d, \phi(N)/p^e) = d$가 되고 따라서 $\ord_N (a^{\phi(N)/p^e}) = 1 \Leftrightarrow a^{\phi(N)/p^e} \equiv 1$이 된다. $\phi(N)$의 서로 다른 소인수는 최대 $\log N$개 있고, $\phi(N)$은 각 소인수를 최대 $\log_p N$개 가질 수 있으므로 $\phi(N)$의 소인수분해를 미리 전처리해두면 $\log^2 N$에 각 $a$의 위수를 구할 수 있다.
2번 쿼리
위수가 $e$인 원소를 출력하는 쿼리이다. $e \nmid \lambda(N)$이라면 Theorem 6에 의해 그러한 원소가 존재하지 않는다. 그렇지 않다면, 다음과 같은 방법으로 위수가 정확히 $e$인 원소를 구할 수 있다.
먼저 모든 $\phi(N)$의 소인수 지수 $p^e$에 대해 위수가 $\lambda(p^e)$인 원소 $g_p$를 구한다. $p = 2, e \geq 3$이라면 $g_p = 5$이고, $p \neq 2$ 또는 $e < 3$이라면 원시근을 하나 구해야 한다. 원시근을 구할 수 있는 닫힌 꼴의 공식은 알려져 있지 않지만, Theorem 3에 의해 $\ZnZ[p^e]$에 $\phi(\phi(p^e))$개의 원시근이 있음이 보장되므로 랜덤한 원소를 하나 골라서 1번 쿼리에서 사용한 것과 같이 위수를 체크해주면 충분히 빠른 시간 내에 원시근을 하나 구할 수 있다. 굳이 랜덤이 아니라 2부터 차례차례 올라가는 식으로 하더라도 충분하다.
이제 구한 모든 근들을 CRT를 통해 $\ZnZ[N]$로 합쳐 준다. 이 원소를 $g$라고 하면, $\ord_N g = \lambda(N)$이다. 이를 $\lambda$-root라 한다. 이제 주어진 $e$에 대해 $g^{\lambda(N)/e}$를 구해 주면, $\ord_N (g^{\lambda(N)/e}) = \dfrac{\lambda(N)}{\gcd(\lambda(N), \lambda(N)/e)} = e$가 됨을 알 수 있다. 마찬가지로 $\lambda(N)$과 $g$를 미리 구해준다면 쿼리당 $\log N$에 위수가 $e$인 원소를 구할 수 있다.
3번 쿼리
슬슬 복잡해지기 시작한다. $N$이 소수였다면 단순히 $\phi(N)$을 구하면 되는 쉬운 문제였겠지만, $N$이 합성수일 수 있기에 다른 방법을 사용해야 한다. \(\psi(e, G) := \vert \{ x : x \in G, \ord x = e \} \vert\)로 정의하자. 즉 $\psi(e, G)$는 $\ord x = e$인 $x \in G$의 개수이다. 우리가 구해야 할 것은 $\psi(e, (\ZnZ[N])^\times)$이다. 또한 \(S(e, G) := \vert \{ x : x \in G, x^e = 1 \} \vert\)로 두자. 이는 $G$ 위에서의 $x^e = 1$의 해의 개수이다. $x^e = 1$이라면 $\ord x \mid e$이므로,
\[\sum_{d \mid e} \psi(d, G) = S(e, G)\]가 성립한다. 또한 뫼비우스 반전 공식에 의해
\[\psi(e, G) = \sum_{d \mid e} S(d, G) \mu(e/d)\]임을 알 수 있다. 결과적으로 $S(d, G)$를 구할 수 있다면 $\psi(e, G)$ 역시 알 수 있게 된다.
$G \cong G_1 \times \cdots \times G_k$일 때, $f(x) = 0$ ($x \in G$)의 해의 개수는 \(\prod_{i=1}^k \vert \{x : f(x) = 0, x \in G_i \} \vert\)와 같다. 따라서 $S(e, G) = \prod_{i=1}^k S(e, G_i)$가 된다. 이때 각 $G_i$가 순환군이라면, $x^d = 1$은 $\gcd(\vert G_i \vert, d)$개의 해를 가진다.
앞서 중국인의 나머지 정리에 따라 $(\ZnZ[N])^\times \cong \prod (\ZnZ[p_i^{e_i}])$라는 것을 보였다.
\[(\ZnZ[p_i^{e_i}]) \cong \begin{cases} \ZnZ[\phi(p_i^{e_i})] & \text{if } p_i > 2 \text{ or } e < 3 \\ \ZnZ[2] \times \ZnZ[2^{e-2}] & \text{if }p_i = 2 \text{ and } e \geq 3 \end{cases}\]이므로, 우리는 $(\ZnZ[N])^\times$를 순환군들로 분해할 수 있다! 결과적으로, $(\ZnZ[N])^\times$를 이루는 순환군들의 크기와 뫼비우스 함수를 미리 전처리해두면 이 값을 충분히 빠르게 구할 수 있을 것이다.
조금 더 생각해보자. 어차피 $e \nmid \lambda(N)$이라면 답은 자명히 $0$이다. 따라서 우리가 구해야 할 것은 $e \mid \lambda(N)$인 $e$에 대한 $\psi(e, (\ZnZ[N])^\times)$들이고, 이를 구하기 위해 필요한 것은 각각의 $e$에 대한 $S(e, (\ZnZ[N])^\times)$이다. 사실, $\psi$는 $S$를 (Divisor) Mobius Transform한 결과이다. SOS DP를 알고 있는 사람들은 SOS DP를 비트 대신 각 소인수에 대해 한다고 생각하면 쉽다. 아무튼 이 과정을 통해 전처리를 ${\cal O}(N^{1/3} \log N)$ 정도에 할 수 있다. 각 쿼리는 미리 전처리한 값을 꺼내 쓰면 되므로 ${\cal O}(1)$.
4번 쿼리
이번에는 원소들의 합을 구하는 쿼리이다. 합은 $(\ZnZ[N])^\times$ 곱셈군이 아니라 $\ZnZ[N]$ 환 위에서 정의되므로 순환 부분군 위에서 계산한 값을 $\ZnZ[N]$ 위로 바로 가져올 수 없다는 문제가 있다.
$(\ZnZ[N])^\times \cong G_1 \times \cdots \times G_k$라고 하자. 이때 $f : G_1 \times \cdots \times G_k \rightarrow (\ZnZ[N])^\times$의 isomorphism을 하나 생각하자. 이제 각각의 $i$에 대해 \(f_i(x) := f(1, \dots, 1, \underbrace{x}_{i\text{번째}}, 1, \dots, 1)\)로 정의하자. 이제 다음과 같은 식이 성립한다.
\[\begin{aligned} f(x_1, x_2, \cdots, x_k) & = f((x_1, 1, \cdots, 1) \cdot (1, x_2, 1, \cdots, 1) \cdots (1, \cdots, 1, x_k)) \\ & = f(x_1, 1, \cdots, 1) f(1, x_2, 1, \cdots, 1) \cdots f(1, \cdots, 1, x_k) \\ & = f_1(x_1) f_2(x_2) \cdots f_k(x_k) \end{aligned}\]$f_i(x)$는 $(\ZnZ[N])^\times$의 원소이자 $\ZnZ[N]$의 원소이므로 맘대로 더할 수 있다.
이번에도 비슷하게 뫼비우스 반전 공식을 적용해 보자. \(\sigma(e) := \sum\limits_{\substack{x \in (\ZnZ[N])^\times\\\ord x = e}} x\), \(T(e) := \sum\limits_{\substack{x \in (\ZnZ[N])^\times\\ x^e = 1}} x\)로 정의하자. dl이번에도 역시나
\[\sum_{d \mid e} \sigma(d) = T(e)\]이므로,
\[\sigma(e) = \sum_{d \mid e} T(d) \mu(e/d)\]이다. 이제 $T(d)$를 구해야 한다. $T(d)$는 $x^d = 1$의 해의 합이므로, $\prod G_i \cong G$인 $G_i$에 대해서도 모두 $x^d = 1$을 만족해야 한다. 여기서 각 $G_i$가 순환군이라 가정했으므로 그 생성원(원시근) $g_i$를 생각하자. $g_i$의 위수는 $\vert G_i \vert $이므로 3번 쿼리에서도 보았듯 해는 총 $\gcd(\vert G_i \vert, d)$개가 생길 것이다. (헷갈린다면 Theorem 3을 다시 보자.) 식을 간결히 하기 위해 $c_i := \gcd(\vert G_i \vert, d)$라고 두자.
이러한 $x$들은 위수가 $c_i$인 원소 \(g'_i\)의 거듭제곱으로 생성된다는 것도 알 수 있다. 위수가 $c_i$인 원소를 구하기 위해서 2번 쿼리에서 사용했던 방식과 마찬가지로, $\ord (g_i^{\vert G_i \vert / c_i)})= c_i$라는 것을 이용하자. 이제 \(g'_i = g_i^{\vert G_i \vert / c_i}\)를 거듭제곱하면 서로 다른 $c_i$개의 원소가 나올 것이다. 이들을 $x_{i1}, \cdots, x_{i c_i}$라고 번호를 매기겠다. 즉, \(x_{ij} = (g'_i)^j\)이다.
이제 모든 $G_i$에 대해 $x_{ij}$를 똑같이 구할 수 있을 것이다. 그러나 이걸 하나하나 구하면 매우 많은 연산이 필요해서 오래 걸릴 것이 분명하다. 우리가 구해야 하는 것은 이러한 모든 $x_{ij}$들의 조합을 합한 것이므로, 아래와 같이 식을 쓸 수 있다.
\[\begin{aligned} & \sum_{a_1 = 1}^{c_1} \sum_{a_2 = 1}^{c_2} \cdots \sum_{a_k = 1}^{c_k} f(x_{1a_1}, x_{2a_2}, \cdots, x_{ka_k}) \\ =\ & \sum_{a_1 = 1}^{c_1} \sum_{a_2 = 1}^{c_2} \cdots \sum_{a_k = 1}^{c_k} f_1(x_{1a_1})f_2(x_{2a_2}) \cdots f_k(x_{ka_k}) \\ =\ & \sum_{a_1 = 1}^{c_1} f_1(x_{1a_1}) \sum_{a_2 = 1}^{c_2} f_2(x_{2a_2}) \cdots \sum_{a_k = 1}^{c_k} f_k(x_{ka_k}) \\ =\ & \prod_{i=1}^k \sum_{j = 1}^{c_i} f_i(x_{ij}) = \prod_{i=1}^k \sum_{j = 1}^{c_i} f_i((g'_i)^j) = \prod_{i=1}^k \sum_{j = 1}^{c_i} (f_i(g'_i))^j \end{aligned}\]깔끔한 등비수열의 합 형태가 나왔다! $\bmod N$에서의 등비수열의 합은 분할 정복으로 ${\cal O}(\log N)$에 구할 수 있다는 것이 잘 알려져 있다.
이제 마지막으로 이러한 isomorphism $f$를 찾을 차례이다. 사실 지금까지의 과정을 되돌아보면 쉽게 찾을 수 있다. 역순으로 $(\ZnZ[N])^\times \cong \prod (\ZnZ[p_i^{e_i}])^\times$와 $(\ZnZ[2^e]) \cong \ZnZ[2] \times \ZnZ[2^{e-2}]$의 isomorphism을 생각해 보자. 먼저 어떤 $(x_1, x_2, \cdots, x_k)$를 $\prod (\ZnZ[p_i^{e_i}])^\times \rightarrow (\ZnZ[N])^\times$로 보내기 위해서는 CRT를 사용할 수 있다. 이를 위해서는 $x \equiv x_i \pmod{p_i^{e_i}}$인 $x$를 찾아야 한다. 우리는 어떤 $i$에 대해서만 $x_i$가 1이 아닌 경우만 생각하면 되므로 더 쉬워진다. 일반적인 CRT와 같이 $q_i$라는 계수를 생각하자. \(q_i \equiv \begin{cases} 1 \pmod{p_j^{e_j}} & \text{if } i = j \\ 0 \pmod{p_j^{e_j}} & \text{if } i \neq j \end{cases}\)이다. 이러한 $q_i$는 $N/(p_i^{e_i})$와 그 곱셈 역원을 곱해서 얻을 수 있다. 이제 $f_i(x_i) \equiv x_i \pmod{p_i^{e_i}}$이고, $f_i(x_i) \equiv 1 \pmod{p_j^{e_j}}$이므로 $x = (x_i-1)q_i + 1$이라고 두면 조건을 만족하는 것을 알 수 있다. 일반적인 $p_i^{e_i}$는 그 자체로 순환군이므로 원시근 $g_i$에 대해 $f_i(g_i) = (g_i-1)q_i + 1$라고 두면 여기서 끝난다.
조금 더 복잡한 $(\ZnZ[2^e])^\times$의 경우를 생각해 보자. $e = 1$인 경우에는 원소가 하나밖에 없는 자명군이므로 답에 아무 영향을 끼치지 못한다. $e = 2$인 경우에는 순환군이므로 $g_i = 3$으로 두면 된다. $e \geq 3$인 경우를 살펴보자. 우리는 이미 $\ZnZ[2] \times \ZnZ[2^{e-2}] \rightarrow (\ZnZ[2^e])^\times$의 isomorphism인 $f(x, y) = (-1)^x 5^y$을 알고 있다. 즉, $-1$과 $5$는 $\ZnZ[2]$와 $\ZnZ[2^{e-2}]$의 생성원을 $(\ZnZ[2^e])^\times$에서 나타낸 것이다. 그리고 $-1$과 $5$를 바로 위에서 했던 CRT 과정을 똑같이 거쳐서 $(\ZnZ[N])^\times$로 보내줄 수 있다.
마지막으로 3번 쿼리에서 했던 과정과 똑같이 $T$를 $\sigma$로 변환해주자. 이것도 대략 ${\cal O}(N^{1/3} \log N)$이 걸린다. 역시나 쿼리는 ${\cal O}(1)$에 가능하다. 끝이다!
참고 사항
- 문제에 주어지는 수의 범위가 꽤 크므로 Pollard-rho 등의 큰 수를 소인수분해할 수 있는 알고리즘이 필요하다.
- 이 글을 참고한다면
문제도 도전해볼만 할 것이다. 참고로 꽤나 스포일러가 될만한 글이니 진지하게 도전해볼 생각이 있다면 보지 않는 것을 추천한다. - 구현이 상당히 복잡할 수 있다. 어떤 분은 각 모듈로 클래스를 아예 클래스로 나눠서 구현하셨다고도 하니 참고하자.
- 원시근, 위수와 더불어서 카마이클 $\lambda$ 함수 등도 어려운 수학 문제들에 종종 나오니 알아두면 좋다. 나중에 나도 다시 와서 볼 작정으로 여러 성질들을 꽉꽉 눌러담았다.