题目描述
对于给出的 $n$ 个询问,每次求有多少个数对 $(x,y)$,满足 $a≤x≤b$ ,$c≤y≤d$,且 $gcd(x,y)=k$,$gcd(x,y)$ 函数为 $x$ 和 $y$ 的最大公约数。
样例
in:
2
2 5 1 5 1
1 5 1 5 2
out:
14
3
数据范围
$1≤n≤50000,\\ 1≤a≤b≤50000,\\ 1≤c≤d≤50000,\\ 1≤k≤50000$
闲来无事水个莫比乌斯板子
本题求的是 $\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}[gcd(i,j)=k]$
先讲求$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=1]$
不妨假设这里的$n<m$。
对于gcd这个东西很套路,先设
$$f(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=x]$$
$$g(x)=\sum_{x|d}f(d)$$
其中 $d\leq n$。
代入莫比乌斯反演公式,得到:
$$ f(x)=\sum_{x|d}\mu(\frac{d}{x})g(d)\\ \Rightarrow f(1)=\sum_{1|d}\mu(d)g(d)\\ $$
修改枚举项,可以得到
$$f(1)=\sum_{i=1}^{n}\mu(i)g(i)$$
$\mu(i)$ 再好求不过了,关键在于 $g(i)$ 是个什么东西。
从含义出发,易得到:
$$g(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[x|gcd(i,j)]$$
$$g(x)=\sum_{i=1}^{n/x}\sum_{j=1}^{m/x}[1|\gcd(i,j)]$$
$1|gcd(i,j)$ 显然恒成立,则
$$g(x)=\frac{n}{x}\cdot \frac{m}{x}$$
$O(1)$ 算就可以了。
最后我们求的是
$$Ans=f(1)=\sum_{i=1}^{n}\mu(i)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor$$
所以只需要 $O(n)$ 算 $\mu(i)$ 前缀和即可。
对于这个题,我们由容斥原理可以推得:求解 $\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}[gcd(i,j)=k]$ 其实相当于求解 $\sum\limits_{i=1}^{b}\sum\limits_{j=1}^{d}[gcd(i,j)=k]-\sum\limits_{i=1}^{b}\sum\limits_{j=1}^{c-1}[gcd(i,j)=k]-\sum\limits_{i=1}^{a-1}\sum\limits_{j=1}^{d}[gcd(i,j)=k]+\sum\limits_{i=1}^{a-1}\sum\limits_{j=1}^{c-1}[gcd(i,j)=k]$
看起来吓人,提个 $k$ 除掉之后,代上面推的结论就好了。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+10;
int primes[N],cnt=0;
bool mp[N];
int mu[N],sum_[N];
void init(int n)
{
mu[1]=1;
for(int i=2; i<=n; i++)
{
if(!mp[i])
{
primes[++cnt]=i;
mu[i]=-1;
}
for(int j=1; j<=cnt&&primes[j]*i<=n; j++)
{
int tmp=primes[j]*i;
mp[tmp]=1;
if(i%primes[j]==0)
{
mu[tmp]=0;
break;
}
mu[tmp]=mu[i]*-1;
}
}
for(int i=1; i<=n; i++)
{
sum_[i]=sum_[i-1]+mu[i];
}
}
ll solve(ll a,ll b,ll d)
{
a/=d,b/=d;
ll mina=min(a,b);
ll res=0;
for(int l=1,r; l<=mina; l=r+1)
{
r=min(mina,min(a/(a/l),b/(b/l)));
res+=(sum_[r]-sum_[l-1])*(ll)(a/l)*(b/l);
}
return res;
}
int main()
{
init(5e4);
int n;
scanf("%d",&n);
while(n--)
{
ll a,b,c,d,k;
scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
ll ans=solve(b,d,k)-solve(b,c-1,k)-solve(a-1,d,k)+solve(a-1,c-1,k);
printf("%lld\n",ans);
}
return 0;
}