Atcoder Regular Contest 106 A ( Python (3.8.2)) - 競技プログラミング日記

おはこんばんにちは！
茶コーダーになって初めての記事です。ARCに精進した成果が出た問題が出たので紹介したいと思います。

1 問題文
2 頭で考えたこと
3 解法
4 参考コード
5 最後に

1 問題文

問題文
整数 N が与えられます。
$3^A+5^B=N$ を満たす正の整数の組 (A,B) が存在するか判定し、
存在する場合は 1 組求めてください。

制約
$1≤N≤10^{18}$ 入力はすべて整数である。

入力
N

出力
条件を満たす組 (A,B) が存在しない場合は -1 と出力せよ。
存在する場合は A とB を空白区切りで出力せよ。答えが複数存在する場合はどれを出力してもかまわない。

2 頭で考えたこと

これを見た瞬間に思ったことはこれ！！！
atcoder.jp

ABC166のD問題ですが、当時のコンテストではこれは全く見当がつかなく解放すら浮かびませんでした。
パッと見だと「こんなの全部の組み合わせ何通りあるの？」や「for文回すにしてもどこからどこまで？」みたいなことを考えてしまうと思います。
しかし、このような問題は範囲の絞り込みに気づければ簡単に解くことができるのです。
では今回の問題で解説していきましょう。

3 解法

まず、（A, B）の組み合わせが正の整数であることから、AもBも増えたらN（= 解）は単調増加していくことがわかります。
なので、AもBも共に $3^A < N$ と $5^B < N$ を満たす必要があります。
Nの制約は $10^{18}$ ですから整理すると、

$\begin{eqnarray} 3^A &< 10^{18} \\ 5^B &< 10^{18} \end{eqnarray}$

この不等号の切り替わりは

$\begin{eqnarray} 3^{38} &> 10^{18} \\ 5^{26} &> 10^{18} \end{eqnarray}$

ですので、
$1 ≤ A ≤ 37, 1 ≤ B ≤ 25$ であることがわかります。
よって、37*25回で全探索することができるため、満たす解が存在しなければ -1 を出力することで正解できます。

4 参考コード

n = int(input())
for a in range(1,38):
    for b in range(1,26):
        if 3**a + 5**b == n:
            print(a,b)
            exit()
print(-1)

5 最後に

思っている以上にレートが上がっていてとても嬉しいです！！
この調子で緑コーダーを目指して頑張るので、応援よろしくお願いします！
よかったらスターつけてね (^_^)