【競プロ精進ログ】ABC174-C

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC174-C「Repsept」です。

ポイント

素直にwhile文を用いて7,77,777...に対して$K$で割り切れるかどうかを見ていてはオーバーフローしてしまいます。というのも，3番目のサンプルを見ると7が999982桁続いている数字が答えになっていますから，そのような数はコンピュータで表現することは大変だと気づく訳です。そこで，工夫が必要になります。

今回考えられる工夫は「大きい数字は$\bmod K$の世界で考える」です。数字が大きすぎて扱えないのであれば，$\bmod K$の世界で考えることによって大きくても扱う数字は$0$以上$K-1$以下に抑えることができるのです。

今回のケースで言えば，7,77,777...を$\bmod K$で表します。すると，鳩の巣原理から少なくとも$K$回でループに突入することが分かります。すると，7の桁数は高々$K$桁考えれば十分であることが分かります。

特に，競プロでc++を扱う場合には，$\bmod K$の世界で考えるという工夫は頻繁に行います。ですので，今回の問題をきっかけに慣れ親しんでいきたいところです。

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int K, X, ans;
int cnt = 1;

int main(){
  cin >> K;

  // modの世界でK桁まで考えれば十分
  rep(i, K){
    // 末尾に7を足していく
    X = (X*10 + 7) % K;
    // もしmodの世界で0になればそのときの桁数を保存してbreakする
    if (X % K == 0) {
      ans = cnt;
      break;
    }
    // 桁数をインクリメント
    cnt ++;
  }
  // for文を全て実行してもmodの世界で0にならない場合があるので再度modの世界で0になっているかをチェックする
  if (X % K == 0)  cout << ans << endl;
  else cout << -1 << endl;
}