LoginSignup
0
1

More than 3 years have passed since last update.

AtCoder Beginner Contest 174 C問題

Posted at

AtCoderを始めましたが、ABCのA・B問題はほぼ解ける、C問題は運が良ければ解けるというレベルです。
まずはC問題を難なく解けるというの目標に、まずは過去問のC問題までをどんどんやっていってます。

自力では解けなかった問題を、解説を見て、理解した内容の整理とその結果のコードを書いていきたいと思います。

問題

高橋君は K の倍数と 7 が好きです。
7,77,777,… という数列の中に初めて K の倍数が登場するのは何項目ですか?
存在しない場合は代わりに -1 を出力してください。

解けなかった原因

ループで末尾に7を追加して1桁増やしながら、Kで割れたら桁数を出力して終了させればいいかと思ったが、
以下がわからず行き詰まる。


  1. 存在しない場合の判定方法がわからない。
    どこまで7を追加したらもう割り切れる数値が存在しないと判断できるのか

  2. 桁数がどんどん増えていった結果、例えばサンプル3だと10999982の桁数の数値をKで割ることになるのは、やめた方がいいのはわかるけど、
    じゃあどうすればいいのか

解説を見て理解した内容

7が1桁増えるということ

・数値*10+7
 7 → 77      = 7 * 10 + 7
 77 → 777  = 77 * 10 + 7
 777→7777 = 777 * 10 + 7

・Kで割った余りも 余り*10+7
 K=9
  7 % K  = 7
  77 % K = 5
  → (7 * 10 + 7) % K = 5
  
  777 % K = 3
  → (5 * 10 + 7) % K = 3

・余りの数の法則性
 同じ余りのパターンをぐるぐる回り、1順は最大K回
 K = 6
 7 % K     = 1
 77 % K    = 5
 777 % K   = 3
 7777 % K  = 1
 77777 % K = 5

ACしたコード

K = int(input().strip())

a = 7
for i in range(K) :
    b = a%K
    if b == 0 :
        print(i+1)
        exit()

    a = b*10+7
print(-1)
0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1