解説

実装が少し重たいです。

約数列挙

まず、長方形を作るという点から、横(または縦)の長さは $N$ の約数である必要があります。

そこで、あらかじめ約数を列挙しておきます。(約数を求めながらでもよいですが、実装が分かりにくくなります。)

約数はC++ならvectorに、Pythonならlistに入れておくとよいでしょう。

判定問題

さて、各約数ごとに黒く塗りつぶされた部分が木となるかを判定します。

以下、黒く塗りつぶされた部分は頂点として扱います。

木である条件としては、

• 全ての頂点が連結であること
• 閉路をもたない

ことがあります。

これは、DFSで $O(N)$ で求めることができます。

具体的には、最初の頂点から連結成分の個数を数え、その個数が全体と一致していればよいです。

閉路を持つ場合は、移動候補で前の頂点以外に既に探索してある場合なので、そのような場合に個数を $-1$ などで置き換えてしまうと場合分けが不要です。

(最終的に個数が全体の頂点数と異なるようにすればよいです)

計算量

計算量を見積もります。 約数列挙に$O(\sqrt N)$、かかり、約数の個数も$O(\sqrt N)$で抑えることができます。 実際には、$2\times10^4$ までの約数の個数で最大となるのは、高度合成数を考えると $80$ 程と小さいです。

(調べるべき頂点数は高々 $N$ 個なので)

判定部分は、先述のように $O(N)$ でできます。

よって、$O(N\sqrt{N})$ でこの問題を解くことができました。

余談

別解としてUnionFindを用いても解けますね。

みなさんは作問者の意図は汲みましたか？

ここはSyntaxコンですよ