このコンテストのA, Bは九九の問題であった。この問題はそれを制約の範囲でかなり大きい表をイメージする。
が
と大きいので工夫して探索
概要
- 九九のように
のマスがある。
- そのマスの値は
である。
- 2以上の1つ整数
を与える。
のマスからその値のマスに最小のステップで移動したい。
- 最小のステップ数は?
解くときに考えた内容
の結果が同じになったときが存在する。例えば
を与えられたら、以下のようなパターンがある。
もちろん、
のような組も考えられるが探索範囲を限るために
として、探索は
までの範囲で、ステップ数
の最小値を求めればいい。
- 実装上は
までの範囲の探索はいろんなやり方がある。
- 初期値
を適当に決めて、
while i*i <= n:
とするのが感覚的にわかりやすいと思う。 - 他にも
for i in range(2, int(-(-n**0.5//1))+1):
などとする方法もあるけどぱっと見よくわからないのであまり使わない。
- 初期値
- 実装上は
実際には、
が
で割り切れる場合は、
として、都度
とその時までの最小値minvと比較して小さい方を新たにminvなどとすればいい
コード
def main(): n = int(input()) i = 2 minv = int(10**12) while i*i <= n: if n % i == 0: a = i b = int(n / i) minv = min(minv, a+b-2) i += 1 if minv < int(10**12): print(minv) else: print(n-1) if __name__ == '__main__': main()