程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj2301【HAOI2011】Problem b

bzoj2301【HAOI2011】Problem b

編輯:C++入門知識

bzoj2301【HAOI2011】Problem b


2301: [HAOI2011]Problem b

Time Limit:50 SecMemory Limit:256 MB
Submit:2951Solved:1318
[Submit][Status][Discuss]

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

容斥原理+莫比烏斯反演

首先根據容斥原理,可以將一個詢問轉化成四個詢問(a-1,c-1) (a-1,d) (b,c-1) (b,d),每次詢問有多少個數對(x,y)滿足1≤x≤n,1≤y≤m且gcd(x,y)=k。

這個問題等價於有多少個數對(x,y)滿足1≤x小於等於(n/k),1≤y≤(m/k)且x與y互質。

這時候我們就可以考慮莫比烏斯反演了。

令f(i)表示1≤x≤n,1≤y≤m且gcd(x,y)=i的數對(x,y)的個數;g(i)表示1≤x≤n,1≤y≤m且i|gcd(x,y)的數對(x,y)的個數。

那麼顯然有g(i)=(n/i)*(m/i)。

根據莫比烏斯定理有f(i)=∑(i|d) mu(d/i)*g(d)。

這樣枚舉每一個k的倍數,就可以將每次詢問做到O(n)。

但這還是有點慢,於是我們考慮進一步優化。我們維護莫比烏斯函數的前綴和,然後對於(n/i)和(m/i)相同的部分分塊處理,最多有4*sqrt(n)塊。所以單次詢問復雜度就降到O(sqrt(n)),總復雜度為O(n*sqrt(n))。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 50005
using namespace std;
int t,a,b,c,d,k,tot;
int mu[maxn],sum[maxn],pri[maxn];
bool mark[maxn];
inline 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*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void getmu()
{
	mu[1]=1;
	F(i,2,50000)
	{
		if (!mark[i]){mu[i]=-1;pri[++tot]=i;}
		for(int j=1;j<=tot&&pri[j]*i<=50000;j++)
		{
			mark[i*pri[j]]=true;
			if (i%pri[j]==0){mu[i*pri[j]]=0;break;}
			else mu[i*pri[j]]=-mu[i];
		}
	}
	F(i,1,50000) sum[i]=sum[i-1]+mu[i];
}
inline int calc(int n,int m)
{
	if (n>m) swap(n,m);
	int ans=0,pos;
	for(int i=1;i<=n;i=pos+1)
	{
		pos=min(n/(n/i),m/(m/i));
		ans+=(sum[pos]-sum[i-1])*(n/i)*(m/i);
	}
	return ans;
}
int main()
{
	getmu();
	t=read();
	while (t--)
	{
		a=read();b=read();c=read();d=read();k=read();
		a--;c--;
		a/=k;b/=k;c/=k;d/=k;
		int ans=calc(a,c)+calc(b,d)-calc(a,d)-calc(b,c);
		printf("%d\n",ans);
	}
	return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved