出典:2022年日本数学オリンピック予選問題9
各頂点が 1 以上 N 以下の整数に対応するような N 頂点の有向グラフを考えます.
i∣jのとき, 頂点 i から頂点 jへの有向辺があるとします.
m=1∑N(頂点mから頂点Nに至る経路の数) がこの問題の答えになります.
頂点 N に至れるような頂点は N の約数に対応するような頂点しかなく, 制約の範囲内では高々 240 個です.
したがって, N の約数を列挙してからこの経路数をDPなどで求めれば, 実行時間制限内に収まります. N の制約が N≦109 などでもこの方針で十分通ると思います.
(頂点の数を絞らなくても, 辺の本数のオーダーが O(NlogN)なので, 時間計算量もこのオーダーとなり, 間に合うと思います......)
経路 v1v2…vk が, 順列 Pvi=vi+1 (1≦i≦k−1),PN=v1,Pi=i (iは経路に現れない) に対応します.