AtCoder Beginner Contest 144 C - Walk on Multiplication Table【Python】
レーティングが収束してきたようなのでAtCoder ProblemsのRecommendationに取り組んでいきたいと思います。
AtCoder Beginner Contest 144 C - Walk on Multiplication Table
Difficulty320、Solve Probability49%でした。
ACとなったコード
N = int(input()) dn = int(N ** 0.5) ans = float('inf') for i in range(dn, 0, -1): if N % i == 0: i2 = N//i ans = min(ans, i+i2-2) break print(ans)
$$ N\leqq 10^{12} $$ よりNの約数の半分を全探索すれば良いと考えたのは良かったものの最初に
dn = int(N ** 0.5)
ではなく
dn = N//2
としてしまっていました。
また、約数の大きい方からの全探索やbreakはあまり意味がないことに気づきました。