洛谷P2522 [HAOI2011]Problem b 题解
题目链接：P2522 [HAOI2011]Problem b
题意：对于给出的 n n n 个询问，每次求有多少个数对 ( x , y ) (x,y) (x,y)，满足 a ≤ x ≤ b a \le x \le b a≤x≤b， c ≤ y ≤ d c \le y \le d c≤y≤d，且 gcd ? ( x , y ) = k \gcd(x,y) = k gcd(x,y)=k， gcd ? ( x , y ) \gcd(x,y) gcd(x,y) 函数为 x x x 和 y y y 的最大公约数。
一句话题意：
求
∑
i
=
a
b
∑
j
=
c
d
[
gcd
?
(
i
,
j
)
=
k
]
\sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)=k]
i=a∑b?j=c∑d?[gcd(i,j)=k]
根据容斥原理，不妨令
F
(
n
,
m
)
=
∑
i
=
1
n
∑
j
=
1
m
[
gcd
?
(
i
,
j
)
=
k
]
F(n,m) = \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k]
F(n,m)=i=1∑n?j=1∑m?[gcd(i,j)=k]
则答案为
F
(
b
,
d
)
?
F
(
b
,
c
?
1
)
?
F
(
a
?
1
,
d
)
+
F
(
a
?
1
,
c
?
1
)
F(b,d)-F(b,c-1)-F(a-1,d)+F(a-1,c-1)
F(b,d)?F(b,c?1)?F(a?1,d)+F(a?1,c?1)
然后推推柿子
∑
i
=
1
n
∑
j
=
1
m
[
gcd
?
(
i
,
j
)
=
k
]
=
∑
i
=
1
?
n
k
?
∑
j
=
1
?
m
k
?
[
gcd
?
(
i
,
j
)
=
1
]
=
∑
i
=
1
?
n
k
?
∑
j
=
1
?
m
k
?
∑
d
∣
gcd
?
(
i
,
j
)
μ
(
d
)
\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] \\&=\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[\gcd(i,j)=1] \\&=\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum_{d\mid \gcd(i,j)}\mu(d) \end{aligned}
?i=1∑n?j=1∑m?[gcd(i,j)=k]=i=1∑?kn???j=1∑?km???[gcd(i,j)=1]=i=1∑?kn???j=1∑?km???d∣gcd(i,j)∑?μ(d)?
考虑变换求和顺序，得
∑
d
=
1
min
?
(
?
n
k
?
,
?
m
k
?
)
μ
(
d
)
∑
i
=
1
?
n
k
?
[
d
∣
i
]
∑
j
=
1
?
m
k
?
[
d
∣
j
]
\sum_{d=1}^{\min\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor\right)}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}[d\mid i]\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[d\mid j]
d=1∑min(?kn??,?km??)?μ(d)i=1∑?kn???[d∣i]j=1∑?km???[d∣j]
根据
1
～
n
1\sim n
1～n 中
d
d
d 的倍数有
?
n
d
?
\left\lfloor\dfrac{n}{d}\right\rfloor
?dn?? 个，
以及 ? n k d ? = ? ? n k ? d ? \left\lfloor\dfrac{n}{kd}\right\rfloor=\left\lfloor\dfrac{\left\lfloor\frac{n}{k}\right\rfloor}{d}\right\rfloor ?kdn??=?d?kn????
可得
∑
d
=
1
min
?
(
?
n
k
?
,
?
m
k
?
)
μ
(
d
)
?
n
k
d
?
?
m
k
d
?
\sum_{d=1}^{\min\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor\right)}\mu(d)\left\lfloor\dfrac{n}{kd}\right\rfloor\left\lfloor\dfrac{m}{kd}\right\rfloor
d=1∑min(?kn??,?km??)?μ(d)?kdn???kdm??
然后数论分块就好了
时间复杂度 O ( N + Q n ) O(N+Q\sqrt{n}) O(N+Qn?)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(5e4+14)
int prime[N],pcnt,mu[N],sum[N];
bool ck[N];
void Mobius()
{
mu[1]=1;
for(int i=2; i<=N; i++)
{
if(!ck[i])
{
prime[++pcnt]=i;
mu[i]=-1;
}
for(int j=1; j<=pcnt&&i*prime[j]<=N; j++)
{
int pos=i*prime[j];
ck[pos]=1;
if(i%prime[j])
{
mu[pos]=-mu[i];
}else
{
mu[pos]=0;
break;
}
}
}
for(int i=1; i<=N; i++)
sum[i]+=sum[i-1]+mu[i];
}
int Q,a,b,c,d,k;
int solve(int n,int m)
{
int res=0;
n/=k;m/=k;
for(int l=1,r; l<=min(n,m); l=r+1)
{
r=min(n/(n/l),m/(m/l));
res+=(sum[r]-sum[l-1])*(n/l)*(m/l);
}
return res;
}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
Mobius();read(Q);
while(Q--)
{
read(a);read(b);read(c);read(d);read(k);
write(solve(b,d)+solve(a-1,c-1)-solve(b,c-1)-solve(a-1,d));
pc('\n');
}
return 0;
}
转载请说明出处
