クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで解くAtCoder(ABC174:C)

Pythonで解くAtCoder

こんにちは、クルトンです！
この記事では

AtCoderの「AtCoder Beginner Contest 174」のC問題をPythonを使って解説します。

問題のリンクを載せておきます。

解法
- 解説
オイラーの定理
サンプルコード
まとめ

解法

解説が分かりやすかったので、解説を参考にしてください。

解説のオイラーの定理について少しだけ補足しておきます。

解説

https://img.atcoder.jp/abc174/editorial.pdf

オイラーの定理

解説で使われていたオイラーの定理の部分について、もう少し詳しく解説します。

オイラーの定理とは

$「nを自然数、aをnと互いに素な整数としたとき{{a^{\varphi\left({n}\right)}\equiv{1}}\,(mod\,{n})}が成り立つ」$

という定理です。

$\varphi\left({n}\right)$ は $1$ から $n-1$ までの自然数の中でnと互いに素なものの個数を表します。…①

この関数は、オイラーの $\varphi$ 関数と呼ばれています。

そのため、 $10$ と $L$ が互いに素である場合、オイラーの定理より ${{10^{\varphi\left({L}\right)}\equiv{1}}\,(mod\,{L})}$ が成りたちます。

このとき、①より $\varphi\left({L}\right)$ は $1$ から $L-1$ までの自然数の中でLと互いに素なものの個数なので

$\varphi\left({L}\right)\leq{L-1}$

となります。

そのため、 $10^i$ について $i=1,2,...,$ と順に検討していけば遅くとも $i=L\left(\leq9000000\right)$ までには求めるべき整数が見つかることが保証されます。

サンプルコード

Pythonで書いた解答を載せておきます。

まとめ

今回は

一般項を数式で表す

オイラーの定理を使って計算量を見積もる

という問題でした。

ではまたお会いしましょう！さようなら～