[AtCoder] ABC 174 C – Repsept

問題

方針

レプユニット数

レプユニット数とは全ての桁が \( 1 \) である整数です。例えば、\( 1 \)、\( 11 \)、\( 111 \) などです。

レプユニット数は、

\[ U_k = \dfrac{10^k – 1}{9}\]

と表現できます。\( k \) と \( 10 \) が互いに素であるとき、オイラーの定理より、\( 10^{\varphi (k) – 1} – 1 \) は \( k \) の倍数となります。

\( K \) が偶数のとき

\( 7U_k \) の \( 1 \) の位は \( 7 \) なので、\( K \) が偶数のとき \( 7U_k \bmod K = 0 \) となるような \( k \) は存在しません。

\( K = 1 \) のとき

このとき答えは \( 1 \) です。

\( K = 5 \) のとき

レプユニット数を用いると、

\[ 7U_k = \dfrac{7(5^{2k} – 1)}{9} \]

となるので、\( 7U_k \) が \( 5 \) の倍数であるとき、\( 5^{2k} – 1 \bmod 45 = 0\)となる \( k \) が存在しますが、\( 5^{2k} – 1 \bmod 5 = 4 \) なので存在しません。

\( K \) が \( 1 \) と \( 5 \) 以外の奇数であるとき

\[ 7U_k = \dfrac{7(10^k – 1)}{9}\]

\( 7U_k \) が \( K \) の倍数であるとき、\( 7(10^k – 1) \) は \( 9K \) の倍数です。また、

\[ 10^{k} \bmod 9K = (10 \times (10^{k-1} \bmod 9K)) \bmod 9K\]

を利用して計算します。\( k \) と \( 10 \) が互いに素であるとき、オイラーの定理より、\( 10^{\varphi (k) – 1} – 1 \) は \( k \) の倍数となります。

コード