まず以下の問題 (以下問題 \(\alpha\) と呼ぶ) を考えます。

順列 \(Q\) であって、全ての \(n\) について \(nq_n\ge s\) となるものの個数を \(s=1,2,\dots,N\) について数えよ。

\(G(n,s)\coloneqq \left\{d\in[1,N]\cap\mathbb{Z}\mid d\ge\frac{s}{n}\right\}\) とし、\(g(n,s)\coloneqq |G(n,s)|\) とします。

\(s\) を固定すると、問題 \(\alpha\) において \(Q\) の満たすべき条件は全ての \(n\) について \(q_n\in G(n,s)\) です。

\(G(1,s)\subseteq G(2,s)\subseteq\dots\subseteq G(N,s)\) であるため、\(n=1,2,\dots,N\) の順に \(q_n\) を決定していくことを考えれば、 問題 \(\alpha\) の特定の \(s\) に対する答えは

\[A(s)\coloneqq\prod_{n=1}^{N}\left(g(n,s)-n+1\right)\]

となります。次に全ての \(s\) に対してこの問題の答えを求めます。

ここで、\(g(n,s)\) と \(g(n,s+1)\) の差分に注目します。
\(m\in[1,N]\cap\mathbb{Z}\) について、 \(m\in G(n,s)\setminus G(n,s+1)\iff m=\frac{s}{n}\) であるため、 \(g(n,s)\neq g(n,s+1)\) なる \(n\) は \(s\) の約数に限られます。
よって、\(s=1,2,\dots,N\) と変化させた時の全ての \(n\) に渡る \(g(n,s)\) の変化は \(O(N\log N)\) 回です。
以上から、\(A(s)\) の値と各 \(g(n,s)\) の値を管理しながら変化のある場所のみ更新を行う事で、全ての \(s\) に渡る問題 \(\alpha\) の答えが \(O(N\log N)\) で求まります。

本題の解法に移ります。
\(h(n,s)\) を、\(nq_n=s\) かつ \(n\neq m\implies mq_m>s\) なる順列 \(Q\) の個数とします。
求める答えは \(\sum_{s=1}^{\infty}h(n,s)\) です。
実際には \(1\times q_1\le N\) であるため、\(s\) の走る上限は \(N\) までで十分です。
また、\(n\) が \(s\) の約数でない場合明らかに \(h(n,s)=0\) です。

よって、\(n\) が \(s\) の約数の場合の \(h(n,s)\) が求まれば良いです。

結論から述べると、

\[h(n,s)=\frac{A(s+1)}{g(n,s+1)-n+1}\]

です。

これは、

• \(nq_n=s\) かつ \(m\neq n\implies mq_m>s\) なる順列 \(Q\)
• 全ての \(m\) で \(mq_m>s\) なる順列 \(Q\)
  

が \(1\) 対 \((g(n,s+1)-n+1)\) 対応することから分かります。
対応としては、前者の順列 \(Q\) において、\(nq_m>s\) なる \(m\in [n+1,N]\cap N\) を \(1\) つ選んで \(q_n(=n)\) と \(q_m\) をswapさせることで後者の順列が得られます。

以上をまとめると、\(A(s)\) や \(g(n,s)\) を更新しながら、\(n\) が \(s\) の約数になったタイミングで \(h(n,s)\) を取得すれば良いです。

計算量は全体で \(O(N\log N)\) です。