問題:https://atcoder.jp/contests/abc144/tasks/abc144_c
無限に大きい掛け算九九の表のような座標テーブルで、あるNが与えられた時にNが書いてあるマスに移動するための最短経路を求める問題です。全探索してそれぞれのマス目がある位置を探して、その時々の原点からの距離を求めていき最短の経路を探します。全探索して探せば良いですが、Nが10^12とかなり大きいため、そのままやると計算時間が間に合わずTLEします。この場合、√Nだけ探索すれば十分です。N＝a×b、a>bの時、a,bを入れ替えても求めたい経路の長さは変わらないので、√Nまでの数で全探索するだけで用が足りるからです。
√Nなら計算量は最大でも10^6なので十分間に合います。
コード例
import math
N=int(input())
lim=int(math.sqrt(N))
ans=10**13
for i in range(1,lim+1):
if N%i==0:
if ans>abs(i+(N//i)-2):
ans=abs(i+(N//i)-2)
print(ans)平方根を使うのでmathをimportします。答えを代入するansに十分大きい値を入れて初期化しておきます。
iを1〜√Nまでの範囲で全探索します。もしNをiで割り切れるのであれば、その時の商(N//i)とiとの和から2を引いたものが経路の長さになります。これがansより小さい値ならば更新していきます。
最後まで探索し終わったら最も小さい経路を出力すればOKです。