[HAOI2011]Problem b
题目描述
对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
输入输出格式
输入格式：
第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k
输出格式：
共n行，每行一个整数表示满足要求的数对(x,y)的个数
输入输出样例
输入样例#1：
2 2 5 1 5 1 1 5 1 5 2
输出样例#1：
14 3
说明
100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000
题解：莫比乌斯反演+容斥原理+分块
a'=a/k b'=b/k
又根据容斥原理，算出ans1=cal(b/k,d/k),ans2=cal((a-1)/k,d/k),ans3=cal(b/k,(c-1)/k),ans4=cal((a-1)/k,(c-1)/k)
输出的答案就是ans1-ans2-ans3+ans4
可以O(n)时间求解，但总时间复杂度为O(n^2)
似乎无路可走了，但这时出现了一种奇妙的方法，把复杂度降到了O(n√n)
根据上面，答案可以遍历1~min(a',b')求解，但可以发现，一定范围内的[a'/d]是相同的，相同的值共有√n种
处理出μ(d)的前缀和，假设i~pos范围内相同，则有s+=(sum[pos]-sum[i-1])*(a'/i)*(b'/i)
pos可以这么求：pos=min(a'/(a'/i),b'/(b'/i)),想一想，看是不是这样
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 typedef long long lol; 8 bool vis[50001]; 9 int mu[50001],prime[50001]; 10 lol sum[50001]; 11 void get_mobious() 12 {int i,j; 13 memset(vis,0,sizeof(vis)); 14 mu[1]=1; 15 int tot=0; 16 for (i=2;i<=50000;i++) 17 { 18 if (vis[i]==0) 19 { 20 prime[++tot]=i; 21 mu[i]=-1; 22 } 23 for (j=1;j<=tot;j++) 24 { 25 if (i*prime[j]>50000) break; 26 vis[i*prime[j]]=1; 27 if (i%prime[j]==0) 28 { 29 mu[i*prime[j]]=0; 30 break; 31 } 32 else mu[i*prime[j]]=-mu[i]; 33 } 34 } 35 sum[0]=0; 36 for (i=1;i<=50000;i++) 37 sum[i]=sum[i-1]+mu[i]; 38 } 39 lol cal(int x,int y) 40 {int r,i,pos; 41 lol s=0; 42 r=min(x,y); 43 for (i=1;i<=r;i=pos+1) 44 { 45 pos=min(x/(x/i),y/(y/i)); 46 s+=(sum[pos]-sum[i-1])*(x/i)*(y/i); 47 } 48 return s; 49 } 50 int main() 51 {int n,a,b,c,d,k; 52 cin>>n; 53 get_mobious(); 54 while (n--) 55 { 56 scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); 57 lol ans1=cal(b/k,d/k); 58 lol ans2=cal((a-1)/k,d/k); 59 lol ans3=cal(b/k,(c-1)/k); 60 lol ans4=cal((a-1)/k,(c-1)/k); 61 printf("%lld ",ans1-ans2-ans3+ans4); 62 } 63 }