Walk on Multiplication Table [AtCoder Beginner Contest 144 C]

https://atcoder.jp/contests/abc144/tasks/abc144_c

解説

https://atcoder.jp/contests/abc144/submissions/8157943

まず、制約を見ると、掛け算表を作るのは現実的ではない。
Nが書かれているマスはどんなマスだろうと考えたときに、ij=Nを満たすマスであることがわかる。
ここに移動するのにかかる移動回数は(i-1)+(j-1)である。
よって、ij=Nを満たすi,jが列挙できれば、その中での移動回数の最小値を答えればいい。

10¹²という特殊制約は、O(sqrt(N))で解いてほしいというメッセージが込められている。
i,jはNの約数であるため、約数列挙を思いつくほうが早いかもしれない。
i≦jという風に制約を追加すると、iの上限はsqrt(N)になる。
よって、iを1～10⁶くらい前探索して、j=N/iとして整数であれば、条件を満たす。
これでi,jが高速に全探索できるので、あとは移動回数の最小値を求める。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    ll ans = infl;
    rep(i, 1, 1010101) if (N % i == 0) chmin(ans, i + N / i - 2);
    cout << ans << endl;
}