Inverse Divisible Permutation

出典：2022年日本数学オリンピック予選問題9

各頂点が $1$ 以上 $N$ 以下の整数に対応するような $N$ 頂点の有向グラフを考えます. $i\mid j$のとき, 頂点 $i$ から頂点 $j$への有向辺があるとします.

$\displaystyle\sum_{m=1}^{N} \left( 頂点1から頂点mに至る経路の数 \right)$ がこの問題の答えになります.

辺の本数のオーダーは $\mathcal{O} \left(N\log N \right)$なので, この経路数をDPなどで求めれば実行時間制限内に収まります.

---

経路 $v_1 v_2\ldots v_k$ が, 順列 $P_{v_{i+1}} = v_{i} \ (1\leqq i \leqq k-1), P_1 = v_k, P_i = i \ (iは経路に現れない)$ に対応します.