この問題を \(O(\sqrt{N}\log N)\) で解く方法を解説します。Ex問題相当の高度な内容と思われます。

\(ij\) が平方数となる正整数の組 \((i,j)\) は、平方因子を持たない正整数 \(k\) と正整数 \(x,y\) により \((kx^2,ky^2)\) と一意に表すことができます。\(k\) を決めたとき、\(x,y\) は独立にそれぞれ \(\left\lfloor\sqrt{\frac{N}{k}}\right\rfloor\) 通りから選ぶことができるので 、次の問題が解ければ十分です。

問題：\(1\) 以上 \(N\) 以下の整数であって、平方因子を持たない数の集合を \(S\) とする。\(\sum_{k\in S}\left\lfloor\sqrt{\frac{N}{k}}\right\rfloor^2\) を求めよ。

この問題に対して ABC239 Ex Dice Product 2 などと同様のアプローチをしてみましょう。

まず \(\left\lfloor\sqrt{\frac{N}{k}}\right\rfloor\) が同じ値になる \(k\) の状態をまとめます。すなわち、\(S_d\) を「\(\left\lfloor\sqrt{\frac{N}{k}}\right\rfloor=d\)、かつ、\(k\) は平方因子を持たない」という条件を満たす数 \(k\) の集合として、

\(\displaystyle \begin{matrix} \sum_{k\in S}\left\lfloor\sqrt{\frac{N}{k}}\right\rfloor^2&=&\sum_{d}\sum_{k\in S_d}\left\lfloor\sqrt{\frac{N}{k}}\right\rfloor^2\\ &=&\sum_{d}|S_d|d^2 \end{matrix}\)

と変形します。これにより、\(1\leq d \leq \sqrt{N}\) に対して \(|S_d|\) を高速に求める問題に帰着されました。

\(|S_d|\) を高速に求めます。\(d\) が異なる \(S_d\) 同士は明らかに disjointであることに注意すると、\(T_d=\cup_{d'\geq d}S_{d'}\) として、代わりに \(|T_d|\) を求めれば十分です。\(T_d\) は「\(1\) 以上 \(\frac{N}{d^2}\) 以下の整数であって、平方因子を持たない数の集合」となります。そのような集合は、\(1\) 以上 \(\frac{N}{d^2}\) 以下の整数から、平方因子がちょうど \(2^2,3^2,4^2,5^2,\ldots\) であるものを除いたものなので、”除原理”により \(d\) の大きい方から順に計算することができます。

\(d\) は \(1\) 以上 \(\sqrt{N}\) 以下を動きますが、\(\frac{N}{d^2}\) は \(O(N^{1/3})\) 種類の値しかとりません。前述のABC239Ex同様に丁寧に計算量解析を行うと、このアルゴリズム全体は \(O(\sqrt{N}\log{N})\) で動作することが確かめられます。

実装例(C++)

追記

「\(1\) 以上 \(X\) 以下の整数であって、平方因子を持たない数の個数」は式 \(\displaystyle \sum_{d=1}^{\sqrt{X}}\left\lfloor\frac{X}{d^2}\right\rfloor \mu(d)\) を用いて \(O(\sqrt{X})\) で求めることができるので、除原理によるDPを行うことなく、直接 \(|T_d|\) を求めることでも、全体として \(O(\sqrt{N}\log{N})\) が達成できます。(実装略)

さらに、平方因子を持たない \(X\) 以下の数の個数は \(\tilde{O}(X^{2/5})\) で求めることもできるため、全体で \(\tilde{O}(N^{5/11})\) で解くこともできます。(詳細略)