题意：对于正整数n，定义f(n)为n所含质因子的最大幂指数。例如f(1960)=f($2^3 \times 5^1 \times 7^2$)=3, f(10007)=1, f(1)=0。
给定正整数a,b，求$\sum_{i=1}^a \sum _{j=1}^b f(gcd(i,j))$ 。
题解：
$$\sum_{i=1}^a \sum _{j=1}^b f(gcd(i,j)) =\sum_{d=1}^a f(d) \sum_{a=1}^n\sum_{b=1}^m[gcd(i,j)==d] = \sum _{x=1}^{\lfloor \frac{n}{d}\rfloor } \mu(x) \lfloor \frac{n}{xd}\rfloor \lfloor \frac{m}{xd} \rfloor $$
令$T=xd$
$$\begin{aligned} \sum _{x=1}^{\lfloor \frac{n}{d}\rfloor} \mu(x) \lfloor \frac{n}{xd}\rfloor \lfloor \frac{m}{xd} \rfloor =\sum_{T=1}^n \lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T} \rfloor \sum_{x|T} \mu(x)f(\frac{T}{x})\end{aligned}$$
设$g(T)=\sum_{x|T} f(x) \mu(\frac{T}{x})$
显然如果可以搞出$g$的前缀和一类的东西，就可以每次$\sqrt{n}$处理每次询问了。
打个表可以发现$g$的结果是这样的：
|
|
大致上有这样的一个规律：
对于函数$g(T)$，设$T$有$k$个质因子，如果每个质因子的指数不都相同，那么$g$函数值为0；否则当$k$为奇数的时候，$g=1$，为偶数时，$g=0$。
证明：
对于$g(T)=\sum_{d|T} f(d) \mu(\frac{T}{d})$（换成$d$防止混淆），设$T=\prod_{i=1}^k p_i^{x_i}$，$x=\prod_{i=1}^k p_i^{y_i}$，$a=max \{x_i \}$
当所有的$x_i$都等于$a$的时候，因为$\mu(x)$只要$x$里有平方因子就为$0$，所以对$g$有贡献的$d$一定是$T$每个质因子至多除掉一个的时候。
当$d$中还存在至少一个质因子指数为$a$的时候，$f(d)=a$，
$\sum f(d)\mu(\frac{T}{d})=a\times \sum_{i=1}^k C_{k}^i (-1)^{k-i} = a\times (\sum_{i=0}^k C_{k}^i (-1)^{k-i} - (-1)^k) = a\times (-1)^{k+1}$
当$d$中所有质因子指数都为$a-1$的时候，$f(d)=a-1$，
$\sum f(d)\mu(\frac{T}{d}) = (a-1) \times (-1)^k$
两者相加得到$(-1)^{k+1}$
当不是所有的$x_i$都等于$a$的时候
当$d$中还存在一个质因子指数等于$a$的时候，设$T$中有$q$个等于$a$，$f(d)=a$
$\sum f(d)\mu(\frac{T}{d})=a \times \sum_{i=1}^{q} C_{q}^i (-1)^{q-i} \sum_{j=0}^{k-q}(-1)^j $，$\sum_{j=0}^{k-q}(-1)^j =(1-1)^{k-q}=0$，所以为$0$
$f(d)=a-1$h时，
$\sum f(d) \mu(\frac{T}{d}) = (a-1) \times (-1)^q \sum_{j=0}^{k-q} C_{k-q}^j (-1)^j =0$
两者相加等于$0$
故只有$T$中所有质因子指数相等的时候才有值，值为$(-1)^{k+1}$。
这样就可以线性筛$g(T)$，由于要处理一个数的次幂的情况，所以可能要有个$log$，求个前缀和，每次询问分块出解即可。复杂度$O(n + \sqrt{n}logn+ q \sqrt{n})$
|
|