🌟

ABC 174 | C - Repsept

2020/11/01に公開約1,100字

問題

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

考えたこと

a_ii番目の数列とすると以下である。

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;
}

参考

Discussion

ログインするとコメントできます