[BZOJ2301][HAOI2011]Problem b 莫比乌斯反演+容斥

2301: [HAOI2011]Problem b

Time Limit: 50 Sec Memory Limit: 256 MB
Submit: 6232 Solved: 2856
[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

Source

同BZOJ1101

在之后再加一个容斥，详见代码

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<cstdio>
 6 #include<algorithm>
 7 #define maxn 50000
 8 #define LL long long
 9 using namespace std;
10 bool vis[maxn];
11 int prime[maxn],cnt,u[maxn],sum[maxn];
12 void init() {
13     u[1]=sum[1]=1;
14     for(int i=2;i<maxn;i++) {
15         if(!vis[i]) prime[++cnt]=i,u[i]=-1; 
16         for(int j=1;i*prime[j]<maxn&&j<=cnt;j++) {
17             vis[i*prime[j]]=1;
18             if(i%prime[j]==0) {u[i*prime[j]]=0;break;}
19             u[i*prime[j]]=-u[i];
20         }
21         sum[i]=sum[i-1]+u[i];
22     }
23     return ;
24 }
25 int a,b,c,d,k,t;
26 LL f(int n,int m,int k) {
27     LL ans=0;
28     n/=k;m/=k;
29     for(int i=1,lst;i<=min(n,m);i=lst+1) {
30         lst=min(n/(n/i),m/(m/i));
31         ans+=(LL)(n/i)*(m/i)*(sum[lst]-sum[i-1]);
32     }
33     return ans;
34 }
35 int main() {
36     init();
37     scanf("%d",&t);
38     while(t--) {
39         scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
40         printf("%lld
",f(b,d,k)-f(a-1,d,k)-f(b,c-1,k)+f(a-1,c-1,k));
41     }
42      
43 }

View Code

O(∩_∩)O~ (*^__^*) 嘻嘻…… O(∩_∩)O哈哈~