BZOJ 2301 [HAOI2011]Problem b

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

都是抄的，伤心。 #include<algorithm> #include<iostream> #include<cstdio> using namespace std; const int N=50005; int T,tot,l=50000,p[N]; bool vis[N]; long long a,b,c,d,k,miu[N],sum[N]; long long query(long long n,long long m) { n/=k,m/=k; long long res=0,nxt; for(long long i=1;i<=min(n,m);i=nxt+1) { nxt=min(n/(n/i),m/(m/i)); res+=(n/i)*(m/i)*(sum[nxt]-sum[i-1]); } return res; } int main() { miu[1]=1; for(int i=2;i<=l;i++) { if(!vis[i]) p[++tot]=i,miu[i]=-1; for(int j=1;j<=tot&&p[j]*i<=l;j++) { vis[p[j]*i]=1; if(i%p[j]==0) { miu[p[j]*i]=0; break; } miu[p[j]*i]=-miu[i]; } } for(int i=1;i<=l;i++) sum[i]=sum[i-1]+miu[i]; scanf("%d",&T); while(T--) { scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k); printf("%lld\n",query(b,d)-query(a-1,d)-query(b,c-1)+query(a-1,c-1)); } return 0; }