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

[HAOI2011]Problem b 题解

2024-09-01 19:43:20   220人阅读

题目大意：

　　对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y)=k。

思路：

　　设f(k)为当1≤x≤n，1≤y≤m，且n≤m，使gcd(x,y)=k的数对(x,y)的对数，g(k)为当1≤x≤n，1≤y≤m，且n≤m，使k|gcd(x,y)的数对(x,y)的对数。则技术分享，莫比乌斯反演，得技术分享。技术分享和技术分享会有连续的一段相同且相同的为一定连续的一段，可证最多有2√n和2√m段，分块处理，对于每个询问可O(√n)解决。

 

代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int M=50009;
 5 int k,prime[M],mu[M],s[M];
 6 bool flag[M];
 7 
 8 int read()
 9 {
10     int x=0; char ch=getchar();
11     while (ch<‘0‘ || ch>‘9‘) ch=getchar();
12     while (ch>=‘0‘ && ch<=‘9‘) x=(x<<1)+(x<<3)+ch-48,ch=getchar();
13     return x;
14 }
15 
16 void getmu(int n)
17 {
18     mu[1]=1;
19     int i,j,k,cnt=0;
20     for (i=2;i<n;++i)
21     {
22         if (!flag[i]) prime[++cnt]=i,mu[i]=-1;
23         for (j=1;j<=cnt && (k=i*prime[j])<n;++j)
24         {
25             flag[k]=1;
26             if (!(i%prime[j])) { mu[k]=0; break; }
27             mu[k]=-mu[i];
28         }
29     }
30     for (i=1;i<n;++i) s[i]=s[i-1]+mu[i];
31 }
32 
33 int sum(int n,int m)
34 {
35     if (n>m) swap(n,m);
36     n=n/k,m=m/k;
37     int i,j,ans=0;
38     for (i=1;i<=n;i=j+1)
39     {
40         j=min(n/(n/i),m/(m/i));
41         ans=ans+(s[j]-s[i-1])*(n/i)*(m/i);
42     }
43     return ans;
44 }
45 
46 int main()
47 {
48     getmu(M);
49     for (int T=read();T;--T)
50     {
51         int a=read(),b=read(),c=read(),d=read();k=read();
52         printf("%d\n",sum(b,d)-sum(a-1,d)-sum(c-1,b)+sum(a-1,c-1));
53     }
54     return 0;
55 }

 

 

 

 

 

[HAOI2011]Problem b 题解


联系
我们