动态几何问题

转化模型。题目中给kx=sqrt(a),yl=sqrt(b)是因为射影定理。

延长kx作hl垂直于kx

易证xylh为矩形,$S_{klcd}=kz^2=kh^2+hl^2=a+b+1+2sqrt{ab}$

所以题目就是让求ab为完全平方数的数对。

暴力枚举时间复杂度不可接受。

设一个数的平方特征为n/最大平方因子,则发现当两个数的平方特征相同,则他们的乘积为完全平方数。

枚举平方特征,则一个范围合法的个数为dx^2<=n的个数。

实际上,一个数没有平方因子的充要条件为mu(x)^2=1,这样子可以列出答案式子为

用整除分块算这个式子。在跳的时候只需要跳min(n/i,m/i)即可。

前面的mu(i)^2可以使用容斥计算。

枚举减去的数可得

(实际上,mu也是容斥系数)

这样子要线性筛前面的数,所以要sqrt(n)的时间复杂度,卡一卡就能过。

实际上如果直接搞会MLE,需要把mu的前缀和存成short,mu存成char才能过。

原文地址:https://www.cnblogs.com/cszmc2004/p/12985882.html