AtCoder Beginner Contest 222 G 問題 222

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

以下を満たすような正の整数 $n$ は存在するか? 存在するならば, そのような整数のうちの最小値を求めよ.

$\underbrace{22 \cdots 2}_{n 個}$ が $K$ の倍数

※ $T$ 個のマルチケース

制約

$1 \leq T \leq 200$
$1 \leq K \leq 10^8$

解法

$\underbrace{22 \cdots 2}_{n 個}=\dfrac{2}{9}(10^n-1)$ である. ここで, 求めるべきは $\dfrac{2}{9}(10^n-1) \equiv 0 \pmod{K}$ となる整数である. ここで, 合同式について, 以下のような性質がある. ただし, $x,y,a$ を整数, $m$ を正の整数とする.

$x \equiv y \pmod{m} \iff ax \equiv ay \pmod{am}$
$a,m$ が互いに素のとき, $x \equiv y \pmod{m} \iff ax \equiv ay \pmod{m}$

このことから,

$\begin{align} \dfrac{2}{9}(10^n-1) \equiv 0 \pmod{K} & \iff 2(10^n-1) \equiv 0 \pmod{9K} \\ & \iff \begin{cases} 10^n-1 \equiv 0 \pmod{\frac{9K}{2}} & (K: 偶数) \\ 10^n-1 \equiv 0 \pmod{9K} & (K: 奇数) \end{cases}\\ & \iff \begin{cases} 10^n \equiv 1 \pmod{\frac{9K}{2}} & (K: 偶数) \\ 10^n \equiv 1 \pmod{9K} & (K: 奇数) \end{cases}\\ \end{align}$

より, $L$ を

$L=\begin{cases} \frac{9K}{2} & (K: 偶数) \\ 9K & (K: 奇数) \end{cases}$

とすると,

$\dfrac{2}{9}(10^n-1) \equiv 0 \pmod{K} \iff 10^n \equiv 1 \pmod{L}$

になる.

剰余環 $\mathbb{Z}/L\mathbb{Z}$ への自然な全射を $\pi: \mathbb{Z} \to \mathbb{Z}/L \mathbb{Z}$ とし, $x \in \mathbb{Z}$ に対して, $[x]:=\pi(x)$ とする. このとき, 問題は $[10]^n=[1]$ を満たす整数を探す問題になる.

$[10]^n=[1]$ となる正の整数 $n$ が存在することと, $[10] \in (\mathbb{Z}/L\mathbb{Z})^\times$ であることは同値である.

(証明)

$[10]^n=[1]$ となる正の整数 $n$ が存在するならば, $[y]:=[10]^{n-1}$ とすると, $n \geq 1$ より, well-defined で, $[x][y]=1$ で, $[x]^{-1}=[y]$ である.
$[10] \in (\mathbb{Z}/L\mathbb{Z})^\times$ のとき, $[10],[10]^2, \dots, [10]^{L+1}$ の中には鳩ノ巣原理から, $1 \leq p \lt q \leq N+1$ で, $[10]^p=[10]^q$ となる整数 $p,q$ が存在する. $[10] \in (\mathbb{Z}/L\mathbb{Z})^\times$ より, $[10]^p \in (\mathbb{Z}/L\mathbb{Z})^\times$ なので, $[10]^{q-p}=[1]$ である.

そして, 剰余環について, 以下の重要な事実がある.

$[x] \in (\mathbb{Z}/L\mathbb{Z})^\times \iff x,L$ は互いに素

よって, $10,L$ が互いに素でないときは $[10]^n=[1]$ を満たす整数 $n$ は存在しない. ただし, $10,L$ が互いに素なことと, $L$ が $2$ の倍数でないかつ, $5$ の倍数でないことは同値である.

ここから, $10,L$ は互いに素とする. このとき, $[10]^n=[1]$ となる整数 $n$ は存在する. さて, $(\mathbb{Z}/L\mathbb{Z})^\times$ は積を演算として群になる. よって, 今, この問題は $(\mathbb{Z}/L\mathbb{Z})^\times$ における $[10$ ] の位数 $\operatorname{ord}([10])$ を求める問題に帰着できる.

特に, 群について, 以下のような重要な事実がある. 以下ではそれを列挙する. ただし, $G$ を群, $H$ を $G$ の部分群とする.

$G$ の元 $x \in G$ に対して, $\langle x \rangle:=\{x^m \in G \mid n \in \mathbb{Z} \}$ は $G$ の部分群である.

(Lagrange) $G$ が有限群であるとき, $H$ も有限群であるが, $H$ の元の個数 $\# H$ は, $G$ の元の個数 $\#G$ の約数である.

(Lagrange) $x \in G$ に対して, $\operatorname{ord}(x)=\# \langle x \rangle$

これらのことから, 以下のことを導ける.

$x \in G$ に対して, $\operatorname{ord}(x)$ は $\# G$ の約数である.

今, $[10] \in (\mathbb{Z}/L\mathbb{Z})^\times$ より, $\operatorname{ord}([10])$ は $\# (\mathbb{Z}/L\mathbb{Z})^\times$ の約数である. 今, $\# (\mathbb{Z}/L\mathbb{Z})^\times$ は $1,2, \dots, L$ の約数のうち, 互いに素な整数の個数 $\varphi(L)$ であるが, $\varphi(L)$ は以下の様にして求めることができる.