【BZOJ2671】Calc
题面
BZOJ
给出N，统计满足下面条件的数对(a,b)的个数：
1.(1le alt ble N)
2.(a+b)整除(a*b)
我竟然粘了题面！！！
题解
还是今天菊开讲的。
设出(d=gcd(a,b))
那么，设(a=xd,b=yd,gcd(x,y)=1)
((x+y)d|xyd^2,x+y|xyd)
根据辗转相减的原理
可以得到(gcd(x+y,x)=gcd(x+y,y)=gcd(x,y)=1)，所以(x+y|d)。
设(d=k(x+y))，因为(a<b)，所以(x<y)，因为(d=k(x+y)le n)
而(b=yd=yk(x+y)le n)
所以确定了(x,y)之后，有(frac{n}{y(x+y)})个(d)
根据上面的式子，还可以知道(yltsqrt n)
所以，我们要求的就是
[sum_{x=1}^{sqrt n}sum_{y=x+1}^{sqrt n}[gcd(x,y)=1]frac{n}{y(x+y)}
]
这样直接算的复杂度是(O(nlogn))
发现(gcd)的形式非常可以莫比乌斯反演
先把(x,y)反过来
[sum_{y=1}^{sqrt n}sum_{x=1}^{y-1}[gcd(x,y)=1]frac{n}{y(x+y)}
]
直接莫比乌斯反演化简
[sum_{d=1}^{sqrt n}mu(d)sum_{y=1}^{sqrt n}sum_{x=1}^{y-1}frac{n}{yd^2(x+y)}
]
复杂度？假的，直接艹吧。。
#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
#define MAX 111111
int n,m;ll ans;
bool zs[MAX];
int pri[MAX],mu[MAX],tot;
ll Calc(int n,int m)
{
ll ret=0;
for(int i=1;i<=m;++i)
{
int t=n/i;
for(int j=i+1,k;j<(i<<1)&&j<=t;j=k+1)
k=min((i<<1)-1,t/(t/j)),ret+=1ll*(k-j+1)*(t/j);
}
return ret;
}
int main()
{
cin>>n;m=sqrt(n);mu[1]=1;
for(int i=2;i<=m;++i)
{
if(!zs[i])pri[++tot]=i,mu[i]=-1;
for(int j=1;i*pri[j]<=m;++j)
{
zs[i*pri[j]]=true;
if(i%pri[j])mu[i*pri[j]]=-mu[i];else break;
}
}
for(int i=1;i<=m;++i)if(mu[i]!=0)ans+=mu[i]*Calc(n/i/i,m/i);
cout<<ans<<endl;return 0;
}