操作は次のように言い換えられます．

• \((1,2,\cdots,N)\) の順列 \(P\) を選び，\(v=P_i\) について操作をする． ただし，\(S\) 内に \(v\) がある場合のみ操作回数に加算する．

各値 \(v\) (\(1 \leq v \leq N\)) について，\(v\) に対する操作が操作回数に加算される確率を考えます．

\(v\) の約数の個数が \(D_v\) 個だとすると，この \(D_v\) 個の中で最初に選ばれる数が \(v\) であることが必要であり，かつ十分です．

よって求めるべきは，\(\sum_{1 \leq v \leq N} 1/D_v\) の値です．

\(f(v)=1/D_v\) とおくと，\(f(v)\) は乗法的関数になっています． そこで，乗法的関数の和を高速に求めるアルゴリズムを用いればこの問題を解くことができます．

使用するアルゴリズムによりますが，計算量は例えば \(O(N^{3/4})\) です．

回答例(C++)

ところで，乗法的関数の和を求めるアルゴリズムを知らなくてもこの問題を解くことは可能です． 適切な間隔で各 \(N\) に対する答えを埋め込み，入力との差分を計算すれば良いです． 埋め込むためのデータを計算する際には，区間篩などのアルゴリズムを用いると十分高速です．