首页 > 代码库 > hdu 1695 容斥原理或莫比乌斯反演
hdu 1695 容斥原理或莫比乌斯反演
GCD
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5310 Accepted Submission(s): 1907
Problem Description
Given 5 integers: a, b, c, d, k, you‘re to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you‘re only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.
Yoiu can assume that a = c = 1 in all test cases.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.
Yoiu can assume that a = c = 1 in all test cases.
Input
The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.
Output
For each test case, print the number of choices. Use the format in the example.
Sample Input
21 3 1 5 11 11014 1 14409 9
Sample Output
Case 1: 9Case 2: 736427
Hint
For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).
Source
2008 “Sunline Cup” National Invitational Contest
题目大意:求在1<=x<=b,1<=y<=d上gcd(x,y)=k的(x,y)对数。
1 /************容斥原理*************/ 2 #include <iostream> 3 #include <cstdio> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 8 typedef __int64 LL; 9 const int maxn=1e5+5; 10 int phi[maxn],prime[maxn],factor[50],num; 11 bool flag[maxn]; 12 void swap(int &a,int &b){ int t=a;a=b;b=t;} 13 14 void init()//欧拉筛选 15 { 16 memset(flag,true,sizeof(flag)); 17 phi[1]=1; 18 for(int i=2;i<maxn;i++) 19 { 20 if(flag[i]) 21 { 22 prime[num++]=i; 23 phi[i]=i-1; 24 } 25 for(int j=0;j<num&&i*prime[j]<maxn;j++) 26 { 27 flag[i*prime[j]]=false; 28 if(i%prime[j]==0) 29 { 30 phi[i*prime[j]]=phi[i]*prime[j]; 31 break; 32 } 33 else phi[i*prime[j]]=phi[i]*(prime[j]-1); 34 } 35 } 36 } 37 38 void getfactor(int n,int &len)//质因数分解 39 { 40 int t=sqrt(n*1.0);len=0; 41 for(int i=0;i<num&&prime[i]<=t;i++) 42 { 43 if(n%prime[i]==0) 44 { 45 factor[len++]=prime[i]; 46 while(n%prime[i]==0) n/=prime[i]; 47 } 48 } 49 if(n>1) factor[len++]=n; 50 } 51 52 int getans(int a,int b) 53 { 54 int n; 55 int ans=0; 56 getfactor(b,n); 57 for(int i=1;i<(1<<n);i++)//容斥原理 58 { 59 int cnt=0,temp=1; 60 for(int j=0;j<n;j++) 61 { 62 if(i&(1<<j)) 63 { 64 cnt++;temp*=factor[j]; 65 } 66 } 67 if(cnt&1) ans+=a/temp; 68 else ans-=a/temp; 69 } 70 return a-ans; 71 } 72 73 int main() 74 { 75 int i,a,b,c,d,k,t,icase=0; 76 LL ans;num=0; 77 init(); 78 scanf("%d",&t); 79 while(t--) 80 { 81 scanf("%d %d %d %d %d",&a,&b,&c,&d,&k); 82 if(k==0||k>b||k>d) 83 { 84 printf("Case %d: 0\n",++icase); 85 continue; 86 } 87 ans=0; 88 b/=k;d/=k; 89 if(b>d) swap(b,d); 90 for(i=1;i<=b;i++) ans+=phi[i]; 91 for(i=b+1;i<=d;i++) ans+=getans(b,i); 92 printf("Case %d: %I64d\n",++icase,ans); 93 } 94 return 0; 95 } 96 /*************莫比乌斯反演****************/ 97 #include <iostream> 98 #include <cstdio> 99 #include <cstring>100 using namespace std;101 102 typedef __int64 LL;103 const int maxn=1e5+5;104 int prime[maxn],mu[maxn],num;105 bool flag[maxn];106 107 void init()108 {109 memset(flag,true,sizeof(flag));110 mu[1]=1;111 for(int i=2;i<maxn;i++)112 {113 if(flag[i])114 {115 prime[num++]=i;mu[i]=-1;116 }117 for(int j=0;j<num&&i*prime[j]<maxn;j++)118 {119 flag[i*prime[j]]=false;120 if(i%prime[j]==0)121 {122 mu[i*prime[j]]=0;123 break;124 }125 else mu[i*prime[j]]=-mu[i];126 }127 }128 }129 130 int main()131 {132 num=0;133 init();134 int i,a,b,c,d,k,t,icase=0;135 scanf("%d",&t);136 while(t--)137 {138 scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);139 if(k==0||k>b||k>d)140 {141 printf("Case %d: 0\n",++icase);142 continue;143 }144 b=b/k;d=d/k;145 if(b>d) swap(b,d);146 LL ans=0,ans1=0;147 for(i=1;i<=b;i++)148 ans+=(LL)mu[i]*(b/i)*(d/i);149 for(i=1;i<=b;i++)150 ans1+=(LL)mu[i]*(b/i)*(b/i);151 ans-=ans1/2;152 printf("Case %d: %I64d\n",++icase,ans);153 }154 return 0;155 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。