#莫比乌斯反演#BZOJ 2671 洛谷 4466 和与积 Calc

本文主要是介绍#莫比乌斯反演#BZOJ 2671 洛谷 4466 和与积 Calc，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

求有多少对$(a,b)$满足$1\le a<b\le n$且$a+b|ab$

---

分析

若$gcd(a,b)=1$,那么$a+b\nmid ab$
若$gcd(a,b)̸=1$,设$d=gcd(a,b),i=da,j=db$
$\therefore (i+j)|ijd$
$\because$若$gcd(a,b)=1$,那么$a+b\nmid ab$
$\therefore (i+j)|d$
也就是求有多少个三元组$(i,j,d)$，满足$id,jd\le n,gcd(i,j)=1,(i+j)|d$
那么$$=\sum _{i=1}^n\sum _{j=1}^{i-1}\lfloor \frac{\lfloor \frac{n}{i}\rfloor }{i+j}\rfloor [gcd(i,j)=1]$$
$$=\sum _{i=1}^n\sum _{j=1}^{i-1}\lfloor \frac{n}{i(i+j)}\rfloor [gcd(i,j)=1]$$
套$$\sum _{k|n}\mu (k)=[n=1]$$
也就是$$=\sum _{i=1}^n\sum _{j=1}^{i-1}\lfloor \frac{n}{i(i+j)}\rfloor \sum _{k|i,k|j}\mu (k)$$
枚举$k$可得
$$=\sum _{k=1}^n\mu (k)\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{i-1}\lfloor \frac{n}{ik(ik+jk)}\rfloor$$
$$=\sum _{k=1}^n\mu (k)\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{i-1}\lfloor \frac{\lfloor \frac{n}{i{k}^2}\rfloor }{i+j}\rfloor$$
Wait，这样不会更慢吗？可以发现$i,j,k$的取值只能在$\sqrt{n}$范围内,所以
$$=\sum _{k=1}^{\sqrt{n}}\mu (k)\sum _{i=1}^{\lfloor \frac{\sqrt{n}}{k}\rfloor }\sum _{j=1}^{i-1}\lfloor \frac{\lfloor \frac{n}{i{k}^2}\rfloor }{i+j}\rfloor$$
洛谷dalao证明时间复杂度是$O(\sqrt{n}\log n)$,可谓是非常高级了

---

代码

#include <cstdio>
#include <cmath>
#define rr register
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef unsigned uit;
const uit N=47001;
uit prime[N>>3],cnt,n;
int mu[N]; bool v[N];
inline long long answ(uit x,uit y){rr long long ans=0; rr uit t=x<<1;for(rr uit l=x+1,r;l<t;l=r+1){if(!(y/l)) return ans;r=min(y/(y/l),t-1);ans+=(r-l+1)*(y/l);}return ans;
}
signed main(){scanf("%u",&n);rr uit m=sqrt(n); rr long long ans=0;for (rr uit i=1;i<=m;++i){if (i>1){if (!v[i]) prime[++cnt]=i,mu[i]=-1;for (rr uit j=1;j<=cnt&&prime[j]*i<=m;++j){v[i*prime[j]]=1;if (i%prime[j]) mu[i*prime[j]]=-mu[i];else break;}}else mu[i]=1;if (!mu[i]) continue;for (rr uit j=1;j*i<=m;++j)ans+=answ(j,n/(i*i*j))*mu[i];}printf("%lld",ans);return 0;
}

这篇关于#莫比乌斯反演#BZOJ 2671 洛谷 4466 和与积 Calc的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---