Pythonで問題を解いてみる #Python

はじめに

MYJLab Advent Calendar 2022の12日目の記事です。
昨日は@momoyamaさんのOpenCVで画像処理（平滑化）という記事でした。
今日は、AtCoder(いわゆる競技プログラミング)の（たぶん）有名問題を解いてみようという記事です！

Python
Google colaboratory

今回、解いてみる問題はC問題の「Repsept」です！
問題文はこちら→https://atcoder.jp/contests/abc174/tasks/abc174_c
問題文はこの記事に載せてないのでリンクを踏んでください！（著作権の関係）

ここで考察を読む前に是非、問題を読んで考えてみてください！!

では、考察に入ります。
ぱっと問題文を読んだ感じ、7,77,777,...を無限に探索する必要があり、膨大な処理が発生しそうですよね。
でも安心してください！この問題は鳩ノ巣原理というものを利用して考えれば簡単（K項目目までの探索）に解くことが出来ます！

鳩ノ巣原理とは...

まあ、当たり前のことを言っているだけなんですが、これが中々奥深いんですね。興味のある人は調べてみてください。

で、この原理がどう役に立たせていくのかというのを今から順に書いていきます。

まずは、問題文の「Kの倍数が登場するのは何項目目か」を「Kで割った余りが0になるのは何項目か」と読み替えます。
次に、7,77,777,...をKで割った余りをどのように工夫して計算するのかを考えると、

がわかります。

次に、どこまで計算すればよいかを考えます。
Kで割った余りは0,1,2,...K-1までKパターンしか存在しないことから、
K+1項目目の余りを計算したとき、K項目目までの余りのどれかと必ずかぶってしまいます。

ここで鳩ノ巣原理を使います！！
先ほどの説明も踏まえると、この問題は
n個のグループ　＝　余りの種類
m個のもの　＝　項目の数
と対応しているといえます。

つまり、K項目目まで計算したとき

K項目目までにKで割った余りが0になる項目があった場合、そこで答えを出力する
K項目目までにKで割った余りが0になる項目がなかった場合、Kで割った余りが0になることはない=-1を出力する
(K項目目までに余りが0になることはなかった　＝　K+1項目目以降で余りが0になることはない)

とすればよいわけです！　あっという間でした！

考え方がわかったところで、やっとコーディングに移ります。

入力の受け取り

K = int(input())

Kで割った余りを格納する変数の用意

amari = 0

1項目目からK項目目までKで割った余りの計算

for i in range(1, K + 1):
    amari = amari * 10 + 7

    if amari % K == 0:
        print(i)
        exit()
    amari %= K

print(-1)

考え方を工夫したことで簡単にコーディングすることが出来ました！

K = 101で検証してみました！

結果、4と出力されました。4桁→7777であり、101の倍数ですから無事成功です。