对于本题,我们设f(n)为满足gcd(x,y)=d且1≤x≤n和1≤y≤m的(x,y)的对数.
F(d)为满足d|gcd(x,y)且1≤x≤n和1≤y≤m的(x,y)的对数.
那么,很显然
,反演后得到:
因为题目要求的是gcd(x,y)为质数,那么,我们枚举每一个质数p,然后得到:
如果直接这样做肯定超时,我们必须优化.
我们设T=pd,那么继续得到:
.
可以看出,如果我们可以先预处理出所有的T对应的
的值,那么本题就解决了.
我们设
,sum(x)是g(x)前缀和.
1.如果k整除x,那么μ(kx)=0,g(kx)=μ(x);
2.如果k不整除x,那么μ(kx)=-μ(x),g(kx)=μ(x)-g(x).
[