AtCoder Beginner Contest 174を見直す C - Repsept

C - Repsept

AtCoder初めて5ヶ月目になってやっと、「AtCoder Problems」で問題の難易度がみられることがわかりました。今回はC問題が「緑」で、D問題が「茶色」だった様ですね。通りでC問題難しいわけだ。

問題

整数k（1<=k<=10^6）が与えられるので、
7, 77, 777, 7777, 77777, .....と言う数列の中に初めてkの倍数が登場するのは何項目か？kの倍数が登場しない場合は-1を出力せよ。

結構時間かけたんですが、サンプルが通せなかったので諦めました。

解説をみて作成した解答（CPP）

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

int main() {
   int k;
   cin >> k;
   int x = 7%k;
   set<int> s;
   int i = 1;
   if (k%2 == 0 || k%5 == 0 ) {
       cout << -1 << endl;
       return 0;
   }
   while (s.count(x) == 0) {
       if(x == 0) {
           cout << i << endl;
           return 0;
       }
       s.insert(x);
       x = (x*10+7)%k;
       i++;
   }
   cout << -1 << endl;
   return 0;
}

理解のための解説

7, 77, 777, 7777....の数列は、前の項を10倍して7を足した数の連続になっている（上図左上）
77 = 7*10+7, 777 = 77*10+7みたいな感じで。
数列をkで割った余り（mod）も同様に、前の項を10倍して7を足した数をkで割った余りの連続になる（上図左下）
また、kの倍数が存在しない場合は、上図の様にModの数列がループ（同じ数字が登場する）事になる（上図右）

よって、記載した解答の様になる。