arimattiの競プロ精進日記

競プロ問題の解法を記録していきます

ABC174 C - Repsept を解いてみた

問題リンク

atcoder.jp

問題概要

 7, 77, 777, \cdots という数列の中に初めて  K の倍数が現れるのは何項目か。存在しない場合は代わりに  -1 を出力せよ。

制約

 1 \leq K \leq 10 ^ 6

ポイント

  • 与えられる数列を  a _ i とする。
  • 問題を言い換えると、「 a _ i K で割った余りが  0 になる最小の  i を求めよ」 となる。
  • 従って、 7, 77, 777, \cdots と順番に  K で割った余りが  0 になるかをチェックする。
  • ただし、数列  a _ i は巨大な値になりえるので次のように工夫する必要がある。
  • 足し算、掛け算に対して剰余は計算途中でとっても結果は変わらないため、 a _ i に対して積極的に剰余をとっていくことを考える。
  •  a _ {i+1} = a _ i \times 10 + 7 で表される。 a_ i \% K = r とすると  a _ {i+1} \% K は、 (r \times 10 +7) \% K で求めることができる。これが  0 になるかチェックすればよい。
  • 1 度現れた余りの値が再度現れた時、そこからループに入っているので  -1 を出力する。これは set 等で出現した余りの値を管理すればよい。

感想

数列の上限がなくどうしたらいいかわからなくなるが、高々  K 回チェックすればよい(鳩ノ巣原理)ことに気付けるかがポイントだったと思う。「 K の倍数になるか」といった類の問題はだいたい鳩ノ巣原理を使う印象。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;

int main() {
  int k;
  cin >> k;
  int n = 7;
  set<int> st;
  st.insert(n);
  int ans = 0;
  bool ng = false;
  while (1) {
    ans++;
    if (n%k == 0) break;
    n *= 10;
    n += 7;
    n %= k;
    if (st.count(n)) {
      ng = true;
      break;
    }
    st.insert(n);
  }
  if (ng) ans = -1;
  cout << ans << endl;
  return 0;
}