[洛谷 3455][POI2007]ZAP-Queries

题目链接

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注