题解：P3327 [SDOI2015] 约数个数和
qwertim
·
·
题解
纪念自己独立推出来的第一道（对我来说）比较进阶的莫比乌斯反演题。
这篇题解将会给出一个完全不需要 d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1] 这个结论的做法，希望能给你一些帮助。
题解
推式子！
\begin{aligned}&
\sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij) \\=&
\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|ij}1 \\=&
\sum\limits_{d=1}^{nm}\sum\limits_{i=1}^n\sum\limits_{\frac d{\gcd(d,i)}|j}^m 1\text{（把 }d \text{ 提到外面）}\\=&
\sum\limits_{d=1}^{nm}\sum\limits_{i=1}^n\lfloor\frac{m\gcd(d,i)}d\rfloor\\=&
\sum\limits_{g=1}^n\sum\limits_{g|i}^n\sum\limits_{g|d}^{nm}[\gcd(d,i)=g]\lfloor\frac{mg}d\rfloor \text{（枚举 } g=\gcd(d,i) \text{）}
\end{aligned}
因为 d\le mg 时才有贡献，所以我们可以将 d 的上限改为 mg，然后将整除消去（下式的 i 与 d 都是上式的 \frac 1g 倍）：
\begin{aligned}&=
\sum\limits_{g=1}^n\sum\limits_{i=1}^{\lfloor\frac ng\rfloor}\sum\limits_{d=1}^{m}[\gcd(d,i)=1]\lfloor\frac md\rfloor\\&=
\sum\limits_{g=1}^n\sum\limits_{i=1}^{\lfloor\frac ng\rfloor}\sum\limits_{d=1}^{m}\lfloor\frac md\rfloor\sum\limits_{k|\gcd(i,d)}\mu(k)\text{（有点感觉了！反演一下）}\\&=
\sum\limits_{k=1}^n\mu(k)\sum\limits_{g=1}^{\lfloor\frac nk\rfloor}\sum\limits_{k|i}^{\lfloor\frac ng\rfloor}\sum\limits_{k|d}^{m}\lfloor\frac md\rfloor\text{（把 }k\text{ 提出去，}g\text{ 的上限也相应的变化）}\\&=
\sum\limits_{k=1}^n\mu(k)\sum\limits_{k|d}^{m}\lfloor\frac md\rfloor\sum\limits_{g=1}^{\lfloor\frac nk\rfloor}\sum\limits_{k|i}^{\lfloor\frac ng\rfloor}1\text{（交换求和顺序）}\\&=
\sum\limits_{k=1}^n\mu(k)\sum\limits_{d=1}^{\lfloor\frac mk\rfloor}\lfloor\frac m{kd}\rfloor\sum\limits_{g=1}^{\lfloor\frac nk\rfloor}\lfloor\frac n{kg}\rfloor\text{（依旧消掉整除）}
\end{aligned}
是不是有点眼熟？设 S(x)=\sum\limits_{i=1}^x\lfloor\frac xi\rfloor，则：
然后我们就做完了！$\mu$ 可以 $\mathcal O(n)$ 线性筛预处理，$S(x)$ 可以 $\mathcal O(n\sqrt n)$ 整除分块预处理，求的时候也可以整除分块做到 $\mathcal O(T\sqrt n)$（假设 $n$，$m$ 同阶），显然足够通过本题。
### 代码
这个题没有取模！！！
```cpp
#define int long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
int cnt,pr[50005],mu[50005],S[50005];
bitset<50005>np;
void init(){
mu[1]=1;
fo(i,2,50000){
if(!np[i])pr[++cnt]=i,mu[i]=-1;
fo(j,1,cnt)
if(i*pr[j]>50000)break;
else{
np[i*pr[j]]=1;
if(i%pr[j]==0){mu[i*pr[j]]=0;break;}
mu[i*pr[j]]=-mu[i];
}
mu[i]+=mu[i-1];
}
fo(i,1,50000){
int l=1;
while(l<=i){
int r=i/(i/l);
S[i]+=(r-l+1)*(i/l),l=r+1;
}
}
}
int n,m;
void solve(){
cin>>n>>m;
if(n>m)swap(n,m);
int l=1,ans=0;
while(l<=n){
int r=min(n/(n/l),m/(m/l));
ans+=(mu[r]-mu[l-1])*S[n/l]*S[m/l],l=r+1;
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
cin>>T,init();
while(T--)solve();
return 0;
}
```
神曲推荐：Radium - Sydosys