洛谷 P3455 loj #2652 [POI2007]ZAP-Queries 题解【数学】【莫比乌斯反演】

题目描述

• $1 \le x \le a$
• $1 \le y \le b$
• $\gcd(x,y)=d$

输入输出样例

2
4 5 2
6 4 3


3
2


题解：

$$\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=d]$$

$$f(n)=\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=n]$$

$$g(n)=\sum_{n|d}f(d)$$

\begin{aligned} g(n)&=f(n)+f(2n)+f(3n)+\cdots\\ &=\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=n,2n,3n,\cdots]\\ \end{aligned}

$$g(n)=\sum_{i=1}^a\sum_{j=1}^b[n|\gcd(i,j)]$$

$$g(n)=\sum_{i=1}^{\left\lfloor\frac an\right\rfloor}\sum_{j=1}^{\left\lfloor\frac bn\right\rfloor}[1|\gcd(i,j)]$$

$$g(n)=\sum_{n|d}f(d)$$

$$f(n)=\sum_{n|d}\mu\left(\frac dn\right)g(d)$$

$$f(n)=\sum_{n|d}\mu\left(\frac dn\right)\left\lfloor\frac an\right\rfloor\left\lfloor\frac bn\right\rfloor$$

$$f(n)=\sum_{i=1}^{\min(a,b)/n}\mu(i)\left\lfloor\frac a{in}\right\rfloor\left\lfloor\frac b{in}\right\rfloor$$

Code：

#include<cstdio>
#include<cstring>
int Min(int x,int y)
{return x<y?x:y;}
int pri[50100],mu[50100],cnt=0,sum[50010];
bool is[50100];
int main()
{
memset(is,1,sizeof(is));
is[1]=is[0]=0;
mu[1]=1;
for(int i=2;i<=50000;++i)
{
if(is[i])
{
pri[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&i*pri[j]<=50000;++j)
{
is[i*pri[j]]=0;
if(i%pri[j])
mu[i*pri[j]]=mu[i]*mu[pri[j]];
else
mu[i*pri[j]]=0;
}
}
for(int i=1;i<=50000;++i)
sum[i]=sum[i-1]+mu[i];
int n,a,b,d;
scanf("%d",&n);
while(n--)
{
scanf("%d%d%d",&a,&b,&d);
int up=Min(a,b)/d;
long long ans=0;
for(int i=1;i<=up;++i)
{
int A=a/d/i,B=b/d/i;
int nxt=Min(up,Min(a/d/A,b/d/B));
ans+=(long long)(sum[nxt]-sum[i-1])*A*B;
i=nxt;
}
printf("%lld\n",ans);
}
return 0;
}


Subscribe

/* */