この問題 のように包除原理を適用することで、すべての \(1 \le n \le N\) について以下のような問題を解くことに帰着します。

• 長さが \(n\) で要素が \(1\) 以上 \(M\) 以下である数列 \(B\) であって、 \(B_i \times B_{i+1}\) がすべて平方数であるものの個数

ここで、 \(f(x)\) を \(x=\prod_i p_i^{e_i}\) と素因数分解したときの \(\prod_i p_i^{e_i \bmod 2}\) とします。この時、以下が成り立ちます。

• 条件を満たす数列 \(A\) について、 \(f(A_1)=f(A_2)=\ldots=f(A_N)\)

逆に、上の条件を満たせば数列 \(A\) は条件を満たします。よって、以下の問題を解けばよいです。

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

これはABC254Dの kyopro_friends さんによる解説 の内容であり、ここで述べられている「整数 \(d\) を動かしたとき、 \(\frac{x}{d^2}\) は \(O(x^{1/3})\) 通りの値しかとらない」ことを利用すると、この問題を \(O(N^2\log N + \sqrt{M}\log M + M^{1/3}N)\) で解くことができます。