[P4450] 双亲数 - 莫比乌斯反演,整除分块

时间:2023-03-09 15:48:31
[P4450] 双亲数 - 莫比乌斯反演,整除分块

模板题……

\[\sum\limits_{i=1}^a\sum\limits_{j=1}^b[(i,j)=k] = \sum\limits_{i=1}^a\sum\limits_{j=1}^b[k|i][k|j][({i\over k},{j\over k})=1]=\sum\limits_{i=1}^{a\over k}\sum\limits_{j=1}^{b\over k}[(i,j)=1]
\]

继续化简

\[\sum\limits_{i=1}^{b\over k}\sum\limits_{j=1}^{d\over k}\sum\limits_{t|(i,j)}\mu(t)=\sum\limits_{i=1}^{b\over k}[t|i]\sum\limits_{j=1}^{d\over k}[t|j]\mu(t)=\sum\limits_{t=1}^{max({b\over k},{d\over k})}{\lfloor{{b\over k}\over t}\rfloor}{\lfloor{{d\over k}\over t}\rfloor}\mu(t)
\]

然后上反演整除分块即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005; int pr[N*2],is[N*2],mu[N*2],cnt; signed main() {
mu[0]=mu[1]=1; is[1]=1;
for(int i=2;i<N;i++) {
if(is[i]==0) {
pr[++cnt]=i;
mu[i]=-1;
}
for(int j=1; j<=cnt&&pr[j]*i<N; ++j) {
is[pr[j]*i]=1;
if(i%pr[j]==0) {
mu[pr[j]*i]=0;
break;
}
else {
mu[pr[j]*i]=-mu[i];
}
}
}
for(int i=1;i<N;i++) mu[i]+=mu[i-1]; int a,b,d;
cin>>a>>b>>d;
a/=d; b/=d;
int ans = 0;
int m=min(a,b);
int l=1,r;
while(l<=m) {
r=min(a/(a/l),b/(b/l));
ans+=(mu[r]-mu[l-1])*(a/l)*(b/l);
l=r+1;
}
cout<<ans<<endl;
}