BZOJ-2301: [HAOI2011]Problem b

[文章目录]

Description

对于给出的n个询问,每次求有多少个数对(x,y),满足axbcyd,且gcd(x,y) = kgcd(x,y)函数为xy的最大公约数,1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000

莫比乌斯反演。首先想到可以是前缀和容斥一下得到。然后考虑化简式子:∑i=1aj=1b [gcd(i,j)==k]
=>等价于找k的倍数中gcd为1的:∑i=1a/kj=1b/k [gcd(i,j)==1]
=>令A=a/k,B=b/k.:∑i=1Aj=1B [gcd(i,j)==1]
=>因为∑d|nμ(d)= 1 (n==1) || 0 (n!=1): ∑i=1Aj=1Bd|gcd(i,j) μ(d)
=>再考虑每个μ(d)对答案的贡献,不妨令B<=A : ∑i=1B*μ(i)*⌊A/i⌋*⌊B/i⌋。

其中⌊A/i⌋为1~A中i的倍数的个数,由于i为gcd(1~A,1~B)的约数,所以二者i的倍数的子集合个数乘积就为累计次数。

由于⌊A/i⌋中大部分树都是相同的,所以可以进行分块。A和B都分成√A+√B级别。所以总时间为2*√a的级别。加上预处理mu的前缀和,就能够O(maxa+T√maxa)出解了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int mu[51000],pri[51000],cnt;
bool v[51000];

void quick_mu()
{
	mu[1]=1;
	for(int i=2;i<=50000;i++)
	{
		if(!v[i]) pri[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&i*pri[j]<=50000;j++)
		{
			v[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				mu[i*pri[j]]=0;
				break;
			}
			else mu[i*pri[j]]=mu[i]*-1;
		}
	}
	for(int i=1;i<=50000;i++)
		mu[i]+=mu[i-1];
}
int work(int x,int y)
{
	if(x>y) swap(x,y);
	int b=1,e,re=0;
	while(b<=x)
	{
		e=min(min(y/(y/b),x/(x/b)),x);
		re+=(mu[e]-mu[b-1])*(x/b)*(y/b);
		b=e+1;
	}
	return re;
}
int main()
{
	int T,a,b,c,d,k;
	scanf("%d",&T);
	quick_mu();
	while(T--)
	{
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); 
		c--; a--; a/=k;b/=k;c/=k;d/=k;
		printf("%d\n",work(b,d)-work(b,c)-work(a,d)+work(a,c));
	}
	return 0;
}

发表评论

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