当前位置: 代码迷 >> 综合 >> BZOJ 2301 [HAOI2011] Problem b
  详细解决方案

BZOJ 2301 [HAOI2011] Problem b

热度:61   发布时间:2024-01-19 02:16:59.0

Description

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



Input

第一行一个整数n,接下来n行每行五个整数,分别表示a、b、c、d、k

 

Output

共n行,每行一个整数表示满足要求的数对(x,y)的个数

 

Sample Input

2

2 5 1 5 1

1 5 1 5 2



Sample Output


14

3



HINT



100%的数据满足:1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

莫比乌斯函数+容斥原理~

思路来自:https://wenku.baidu.com/view/fbe263d384254b35eefd34eb.html,讲得非常清晰~

定义一个函数G(a,b,k)表示i<=a,j<=b时gcd(i,j)>=k的个数,那么易知G(a,b,k)=(a/k)*(b/k)(均为下取整)。

所以由容斥原理,答案cal(a,b)=μ(1)*G(a,b,1)+μ(2)*G(a,b,2)+μ(3)*G(a,b,3)+...+μ(a)*G(a,b,a)。(这里假设a<=b)

附一个来自论文的图:


化简得:cal(a,b)=sum{μ(i)*(a/i)*(b/i)},其中i<=a(a<=b),除法均为向下取整,μ(x)为莫比乌斯函数。

到这一步,算法复杂度为O(n),询问<=50000,显然无法胜任。

但是我们知道在一定范围内a/i的大小是一定的。所以我们枚举大小一定的范围,再求和,时间复杂度O(T*2*sqrt(n))。

(主函数写成mian,CE到吐血……我真是……不知道该说些什么……= =)


#include<cstdio>
#include<iostream>
using namespace std;int n,a,b,c,d,k,miu[50001],z[50001],num[50001];
bool bb[50001];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}int cal(int u,int v)
{u/=k;v/=k;if(u>v) swap(u,v);if(!u) return 0;int ne,ans=0;for(int i=1;i<=u;i=ne){ne=min(u/(u/i),v/(v/i))+1;ans+=(num[ne-1]-num[i-1])*(u/i)*(v/i);}return ans;
}int main()
{miu[1]=1;for(int i=2;i<=50000;i++){if(!bb[i]) z[++z[0]]=i,miu[i]=-1;for(int j=1;j<=z[0] && z[j]*i<=50000;j++){bb[i*z[j]]=1;if(i%z[j]) miu[i*z[j]]=-miu[i];else break;}}for(int i=1;i<=50000;i++) num[i]=num[i-1]+miu[i];n=read();while(n--){a=read();b=read();c=read();d=read();k=read();printf("%d\n",cal(b,d)+cal(a-1,c-1)-cal(b,c-1)-cal(a-1,d));}return 0;
} 


  相关解决方案