ABC 174 | C - Repsept

問題

https://atcoder.jp/contests/abc174/tasks/abc174_c

考えたこと

$a_i$を$i$番目の数列とすると以下である。

$$a_i= \begin{cases} 7 & (i=1) \\ 10 a_{i-1}+7 & (i \geq 2) \end{cases}$$

$a_i \bmod 7 = 0$かどうかを求めればいいのだが、$a_i$は容易にlong longを超えてしまうので他に表し方がないか考える。
$a_i$ をそのまま扱わずに$\mod 7$ された状態で扱っても同じなのでそのように扱う。

そうすると$a_i$は0がいずれ現れるか、$1 < a_i \leq K$の範囲で同じ値を繰り返すかである。繰り返しが現れた場合は答えがないことになる。

コード

実装時のTips

• あえてusing mint = modint;を使ったが使わなくてもコードは短くできる

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

using mint = modint;

int main() {
  ll K;
  cin >> K;
  mint::set_mod(K);
  mint a = 7;
  ll count = 1;
  if (a == 0) {
    cout << count << endl;
    return 0;
  }
  unordered_set<int> s;
  s.insert(a.val());
  while (true) {
    count++;
    a = a * 10 + 7;
    if (a == 0) {
      cout << count << endl;
      return 0;
    }
    if (s.find(a.val()) != s.end()) {
      break;
    }
    s.insert(a.val());
  }
  cout << -1 << endl;
}

参考