【Bestcoder #79 div1】C

Bestcoder #79 div1】C"/>

【Bestcoder #79 div1】C

题目描述

定义

F(x)={10x=k2,k∈N∗otherwise $$F(x)= \begin{cases} 1& x=k^2, k\in N^* \\ 0 & otherwise \end{cases}$$

问

∑i=1n∑j=1mF((i,j)) $$\sum_{i=1}^n \sum_{j=1}^m F\Big( (i, j) \Big)$$

n,m≤107 $n, m\leq 10^7$
T $T$组询问，T≤104$T\leq 10^4$

---

分析

原式=∑x=1n⌊nx⌋⌊mx⌋∑p|x,p=k2(k∈N∗)μ(xp) $$原式=\sum_{x=1}^n \left \lfloor \frac{n}{x} \right \rfloor \left \lfloor \frac{m}{x} \right \rfloor \sum_{p|x, p=k^2(k\in N^*)} \mu \left(\frac{x}{p} \right)$$

后面的式子可以预处理，前面的部分是经典的分块，然后就 O(Tn−−√) $O( T\sqrt{n})$做完了。