首页 > 代码库 > [HAOI2011]Problem b

[HAOI2011]Problem b

2024-11-10 13:43:02   203人阅读

题目描述

对于给出的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\n",ans1-ans2-ans3+ans4);
62     }
63 }

 

[HAOI2011]Problem b


联系
我们