题目链接
https://www.luogu.com.cn/problem/P3455
题解
经典的莫比乌斯反演题。
题目要求的是:
$$\sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=d]$$
不妨先设 \(a \leq b\)。
首先除一个 \(d\):
$$\sum_{i=1}^{\left \lfloor \frac{a}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{b}{d} \right \rfloor} [\gcd(i,j)=1]$$
然后根据莫比乌斯函数的性质换元:
$$\sum_{i=1}^{\left \lfloor \frac{a}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{b}{d} \right \rfloor} \sum_{x|\gcd(i,j)}\mu(x)$$
有这样一个性质:若 \(x|\gcd(i,j)\),则 \(x|i\) 且 \(x|j\)。所以我们继续:
$$\sum_{i=1}^{\left \lfloor \frac{a}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{b}{d} \right \rfloor} \sum_{x|i,x|j}\mu(x)$$
枚举 \(x\):
$$\sum_{i=1}^{\left \lfloor \frac{a}{d} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{b}{d} \right \rfloor} \sum_{x=1}^{a}\mu(x)[x|i][x|j]$$
交换求和顺序:
$$\sum_{x=1}^a \mu(x) \sum_{i=1}^{\left \lfloor \frac{a}{d} \right \rfloor} [x|i] \sum_{j=1}^{\left \lfloor \frac{b}{d} \right \rfloor} [x|j]$$
然后继续换元:
$$\sum_{x=1}^{a}\mu(x)\left \lfloor \frac{a}{dx} \right \rfloor\left \lfloor \frac{b}{dx} \right \rfloor$$
这个式子就可以直接算了。
然而直接算的时间复杂度是 \(O(a)\) 的,所以我们需要用整除分块优化一下,从而将时间复杂度优化到 \(O(\sqrt a)\)。
#include <iostream> #include <algorithm> #define N 50000 using namespace std; int mu[50005],vis[50005],pri[50005]; void init() { int cnt=0; mu[1]=vis[1]=1; for(int i=2;i<=N;i++) { if(!vis[i]) mu[i]=-1,pri[++cnt]=i; for(long long j=1;j<=cnt&&pri[j]*i<=N;j++) { int x=pri[j]*i; vis[x]=1; if(i%pri[j]==0) { mu[x]=0; break; } else mu[x]=-mu[i]; } } for(int i=1;i<=N;i++) mu[i]+=mu[i-1]; } int main() { int t; cin>>t; init(); while(t--) { int n,m,d; long long ans=0; cin>>n>>m>>d; if(n>m)swap(n,m); n/=d,m/=d; for(int l=1,r;l<=n;l=r+1) { r=min(n/(n/l),m/(m/l)); ans+=(long long)(mu[r]-mu[l-1])*(n/l)*(m/l); } cout<<ans<<endl; } return 0; }