转化模型。题目中给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才能过。