[AtCoder] ABC 174 C – Repsept

2020年8月3日2020年12月14日

問題

方針

レプユニット数

レプユニット数とは全ての桁が \( 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 \) の倍数となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int K;
    cin >> K;

    if (K == 1) {
        cout << "1\n";
        return 0;
    }
    if (K % 2 == 0 || K % 5 == 0) {
        cout << "-1\n";
        return 0;
    }
    K *= 9;
    int a = 10;
    for (int i = 0; i <= 10 * K; i++) {
        if ((7 * (a - 1 + K)) % K == 0) {
            cout << i + 1 << "\n";
            return 0;
        }
        a = (a * 10) % K;
    }
   
    return 0;
}