数学（莫比乌斯反演）：HAOI 2011 问题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)的个数

样例输入：

2

2 5 1 5 1

1 5 1 5 2

样例输出：

14

3

数据范围：

10%的数据满足：1≤n≤5，1≤a≤b≤100，1≤c≤d≤100

30%的数据满足：1≤n≤10

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

　　令F(n)表示gcd为k的倍数的数对个数，f(d)表示gcd为k个对数，显然符合第二种反演的形式。

　　然后再加上一个计数的小优化就可以AC了。

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int maxn=50010; 6 int prime[maxn],cnt; 7 int mu[maxn],sum[maxn]; 8 bool check[maxn]; 9 10 void Prepare(){ 11 mu[1]=1; 12 for(int i=2;i<=50000;i++){ 13 if(!check[i]){ 14 prime[++cnt]=i; 15 mu[i]=-1; 16 } 17 for(int j=1;j<=cnt;j++){ 18 if(prime[j]*i>50000)break; 19 check[prime[j]*i]=true; 20 if(i%prime[j]==0){ 21 mu[prime[j]*i]=0; 22 break; 23 } 24 mu[prime[j]*i]=mu[i]*-1; 25 } 26 } 27 for(int i=1;i<=50000;i++) 28 sum[i]=sum[i-1]+mu[i]; 29 } 30 31 int T,k; 32 int a,b,c,d; 33 int C(int n,int m){ 34 n/=k;m/=k; 35 int ret=0,p; 36 if(n>m)swap(n,m); 37 for(int i=1;i<=n;i=p+1){ 38 p=min(n/(n/i),m/(m/i)); 39 ret+=(sum[p]-sum[i-1])*(n/i)*(m/i); 40 } 41 return ret; 42 } 43 44 int main(){ 45 freopen("b.in","r",stdin); 46 freopen("b.out","w",stdout); 47 Prepare(); 48 scanf("%d",&T); 49 while(T--){ 50 scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); 51 printf("%d\n",C(b,d)-C(b,c-1)-C(a-1,d)+C(a-1,c-1)); 52 } 53 return 0; 54 }

 

转载于:https://www.cnblogs.com/TenderRun/p/5708072.html

总结

以上是生活随笔为你收集整理的数学（莫比乌斯反演）：HAOI 2011 问题B的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。