문제는 만들어 놓고 풀이는 이제야 씁니다. 사실 시작이 지금(250619)이지 완성은 또 얼마나 뒤에 될지 모르겠습니다.
지문이 복잡하게 쓰인 점에 대해 안타깝게 생각합니다. 실제로 출제 아이디어는 저 표현들에서 출발하긴 했습니다만 결과적으로 $\mathbb{Z}_p[x]$를 감추려고 최선을 다한 것처럼 보여지는 것이 별로네요. 하나씩 설명을 해 보겠습니다.
문제 상황
자릿수 함수 $D_d(n, i)$
자릿수 함수 $D_d(n, i)$는 양의 정수 $n$과 $i$를 받아서 $\displaystyle \left[ \frac{n}{d^i} \right]$을 $d$로 나눈 나머지를 의미합니다. 이는 곧 $n$의 $d$진법 표현에 대해 $i$번째(zero based) 자리 숫자를 리턴하는 것입니다.
받아안올림 덧셈 $\oplus_p$
받아올림은 다들 아실 것 같습니다. 받아안올림 덧셈은 말 그대로 받아올림을 하지 않는 덧셈입니다. 10진법에서의 예시를 들자면 $9876 + 22222 = 21098$인 식입니다. 지문의 정의가 $p$진법에서의 이 연산을 수식으로 나타냄을 알 수 있습니다.
받아안올림 곱셈 $\otimes_p$
받아안올림 곱셈은 설명하기 조금 복잡한데, TODO
받아안올림 거듭제곱
은 단순히 받아안올림 곱셈을 여러 번 하는 것입니다.
$\omega(n; p, N)$
TODO
풀이
1. $(\mathbb{Z}_{\geq 0}, \oplus_p, \otimes_p)$는 ring을 이룹니다.
2. 이 ring은 polynomial ring $\mathbb{Z}_p[x]$와 isomorphic합니다. 이 isomorphism을 $\phi$로 둡시다.
3. $F(x) := \phi(N)$에 대해 $F$로 생성한 아이디얼 $(F)$와 quotient ring $\mathbb{Z}_p[x] / (F)$, 그 projection map $\varphi : \mathbb{Z}_p[x] \to \mathbb{Z}_p[x] / (F)$을 생각합시다.
4. 문제의 집합 $I := \{1 \oplus_p (i \otimes_p N) \mid i \in \mathbb{Z}^+\}$에 대해 $\phi[I] = \varphi^{-1}(1 + F) \setminus \{1\}$입니다.
5. 즉 $\phi[I]$는 $\mathbb{Z}_p[x]$의 원소 중 $(F)$로 만든 quotient ring에 $\varphi$로 project했을 때 multiplicative identity가 되는 원소를 모은 집합입니다. ($1$ 제외)
6. $\omega(n; p, N)$은 $\phi(n)$이 최소 몇 번의 거듭제곱을 해야 $\phi[I]$에 속하게 되는지 묻고 있습니다.
6-1. $n$을 $I$에 속하게 만드는 $k$가 존재한다는 것은 $\varphi(\phi(n))^k = 1 + F$이면서 $\phi(n)^k \neq 1$인 $k$가 존재한다는 것과 동치입니다.
6-2. $n$을 $I$에 속하게 만드는 $k$가 존재하지 않는다는 것은 $\varphi(\phi(n))^k = 1 + F$인 $k$가 존재하지 않는다는 것과 동치입니다.
6-3. 모든 가능한 $n$에 대해 $\phi(n)^k = 1$를 만족하는 $k$가 존재하는 $n$은 $p$개보다 적습니다.
7. 여기서 새 집합 $I'$를 도입합시다. $I' := \phi^{-1}[\varphi^{-1}(1 + F)]$입니다.
7-1. $n$을 $I'$에 속하게 만드는 $k$가 존재한다는 것은 $\varphi(\phi(n))^k = 1 + F$인 $k$가 존재한다는 것과 동치입니다.
7-2. $n$을 $I'$에 속하게 만드는 $k$가 존재하지 않는다는 것은 $\varphi(\phi(n))^k = 1 + F$인 $k$가 존재하지 않는다는 것과 동치입니다.
7-3. $\varphi(\phi(n))$의 곱셈에 대한 cyclic group이 정의되는 경우 그 order가 $k$이고, 정의되지 않는 경우 $k$는 존재하지 않습니다.
8. 이제 $R := \mathbb{Z}_p[x] / (F)$에 대해 $\displaystyle \sum_{f \in R} \text{ord}(f)$를 구하고자 합니다. 여기서 $\text{ord}$가 정의되지 않을 경우 $0$입니다.
9. $R$의 multiplicative group $R^\times := \{r \in R \mid \exists s : rs = 1\}$를 고려합시다.
9-1. $R^\times$의 모든 원소는 곱셈에 대한 cyclic group이 정의되고 그 역도 성립합니다. 따라서 구하고자 하는 값은 $\displaystyle \sum_{f \in R^\times} \text{ord}(f)$이 되었습니다.
10. $F(x)$를 $Z_p[x]$에서의 irreducible polynomial들로 인수분해합시다. $\displaystyle F(x) = \prod_i (f_i(x))^{e_i}$입니다. 모든 $f_i$는 irreducible이고 unique합니다.
11. Chinese Remainder Theorem on Rings에 의해, $\displaystyle R = \mathbb{Z}_p[x]/(F) \cong \prod_i \mathbb{Z}_p[x]/(f_i^{e_i})$입니다.
12. 자연스럽게 $\displaystyle R^\times = ( \mathbb{Z}_p[x]/(F) )^\times \cong \prod_i ( \mathbb{Z}_p[x]/(f_i^{e_i}) )^\times$입니다.
13. 개별 $R_i^\times := (\mathbb{Z}_p[x]/(f_i^{e_i}))^\times$에 대해 살펴봅시다.
14. 임의의 $R_i^\times$에 속한 원소 $f$는 $\mathbb{Z}_p[x]/(f_i)$의 원소 $e_i$개: $( f / f_i^0 \text{ mod } f_i, \ldots, f / f_i^{e_i-1} \text{ mod } f_i)$와 일대일대응됩니다. 여기서 $f / g$는 $f$를 $g$로 나눈 몫입니다.
15. $d_i := \deg(f_i)$로 두면 $ \mathbb{Z}_p[x]/(f_i) \cong \text{GF}(p^{d_i})$이므로, $f_i$를 $t$로 치환하면 $R_i^\times \cong (\text{GF}(p^{d_i})[t] / (t^{e_i}))^\times$입니다.
16. 상수항을 $1$로 고정하고 $\text{GF}(p^{d_i})$의 곱셈 구조를 떼어 $(\text{GF}(p^{d_i})[t] / (t^{e_i}))^\times \cong \text{GF}(p^{d_i})^\times \times (1 + (t\text{GF}(p^{d_i})[t]) / (t^{e_i}))^\times$를 얻습니다.
17. 임의의 $f(t) \in (1 + (t\text{GF}(p^{d_i})[t]) / (t^{e_i}))^\times$을 고려합시다. $f(t)$의 $\text{ord}$를 알아내고자 합니다.
18. $(1 + (t\text{GF}(p^{d_i})[t]) / (t^{e_i}))$는 $p^{d_i(e_i-1)}$개의 원소로 구성되어 있습니다. 따라서 $f$의 $\text{ord}$는 $p$의 지수승 꼴이어야 합니다.
19. $f(t)$의 항 중 상수항이 아니면서 차수가 가장 낮은 항의 차수를 $\text{MD}(f(t))$라고 합시다. 그러한 항이 없으면 $f(t) = 1$이므로 $\text{ord}$는 1입니다.
20. $f(t)$를 $\text{GF}(p^{d_i})[t]$에서 잠시 고려하면, $f^{p^r}(t)$의 $t^{\text{MD}(f(t))}$부터 $t^{\text{MD}(f(t)) p^r-1}$까지의 계수는 모두 $p$의 배수입니다.
21. $\text{char }\text{GF}(p^{d_i}) = p$이므로 $\text{MD}(f^{p^r}(t)) = \text{MD}(f(t)) p^r$입니다.
22. $(1 + (t\text{GF}(p^{d_i})[t]) / (t^{e_i}))$에서 $1$이 아닌 모든 항이 사라지려면 $\text{MD}(f^{p^r}(t))$가 $e_i$ 이상이어야 하고, $\text{MD}(f(t)) p^r \geq e_i$인 최소의 $p^r$이 $\text{ord}$가 됩니다.
23. 이제 $(1 + (t\text{GF}(p^{d_i})[t]) / (t^{e_i}))$에 속하면서 $\text{ord}$가 $p^j$를 나누는 원소의 개수 $S_{d_i, e_i}(p^j)$를 구하고자 합니다.
24. $S_{d_i, e_i}(p^j)$에 의해 카운트되는 각 원소 $f$는 $\text{MD}(f(t)) p^{j} \geq e_i$를 만족해야 하므로 총 $p^{d_i(e_i - \lceil e_ip^{-j} \rceil)}$개입니다.
25. $U(n) := \#\{x \in (\mathbb{Z}_p[x]/\langle f(x)\rangle)^\times \mid \text{ord}(x) | n\}$으로 정의합시다.
26. $U(n) = \prod_{i} \gcd(n, p^{d_i} - 1) \cdot S_{d_i, e_i}(\nu_p(n))$입니다. 여기서 $\nu_p(n)$은 $n$ 약수 중 가장 큰 $p$의 거듭제곱수입니다.
27. $A(n) = \sum_{d|n}\mu\left(\frac{n}{d}\right)U(d)$는 $R^\times$의 원소 중 $\text{ord}$가 정확히 $n$인 원소의 개수입니다.
28. $R^\times$의 모든 원소의 $\text{ord}$의 합 $\Sigma$를 계산합시다.
\begin{align*}
\Sigma &= \sum_{k | | R^\times |} A(k)\cdot k\\
&= \sum_{k|| R^\times |}k\sum_{d|k}\mu\left(\frac{k}{d}\right)U(d)\\
&= \sum_{k|| R^\times |}\sum_{d|k}k\mu\left(\frac{k}{d}\right)\prod_i \gcd(d, p^{d_i}-1)p^{d_i(e_i - \lceil e_i / p^{\nu_p(d)}) \rceil)}\\
&= \sum_{d|| R^\times |}d\prod_i \gcd(d, p^{d_i}-1)p^{d_i(e_i - \lceil e_i / p^{\nu_p(d)}) \rceil)}\sum_{k|\frac{| R^\times |}{d}}k\mu(k)\\
C(d) &:= d\prod_i \gcd(d, p^{d_i}-1)p^{d_i(e_i - \lceil e_i / p^{\nu_p(d)}) \rceil)}\\
M(n) &:= \sum_{k|n} k\mu(k)\\
&= \sum_{d|| R^\times |}C(d)M\left(\frac{| R^\times |}{d}\right)
\end{align*}
29. $M(n)$은 아래와 같이 계산됩니다. $n$의 소인수분해 형태에 대해,
\begin{align*}
n &=: \prod_{i}p_i^{e_i}\\
M\left(\prod_{i}p_i^{e_i}\right) &= M\left(\prod_{i}p_i\right)\\
&= \sum_{S\subset\{p_1,p_2,\ldots\}} (-1)^{|S|} \prod_{p\in S}p\\
&= \prod_i (1-p_i)
\end{align*}
30. 쓰다 보니 귀찮네요. 이거면 충분하겠죠?
https://www.acmicpc.net/problem/33479