RXD and math

题目链接

题意

计算$\sum_{i-1}^{ {n}^{k} } { \mu(i)}^{2} \left \lfloor \sqrt{ \frac{ {n}^{k} }{i} } \right \rfloor.$

思路

赛中是找规律的，规律是比较明显。

根据题解的说法，任意一个数字可以表示成$x={a}^{2} \times b.$其中$b$是不含二次因子的，$| \mu(b)|=1$.

这个式子相当于在枚举$b$，然后问能用$a$和$b$表示成${n}^{k}$以内多少个数字.
对于每一个$b$，$a$有$\left \lfloor \sqrt{ \frac{ {n}^{k} }{i} } \right \rfloor$ 种。
所以相当于所有数字都被数了一遍，答案就是${n}^{k}.$