題目鏈接http://acm.hdu.edu.cn/showproblem.php?pid=1695

看了別人的方法才會做 參考博客http://blog.csdn.net/shiren_Bod/article/details/5787722

題意 a,b,c,d,k五個數，a與c可看做恒為1，求在a到b中選一個數x，c到d中選一個數y，使得gcd(x,y)等于k，求x和y有多少對。

首先可以想到選取的必是k的倍數，假設是x和y倍，則x和y一定是互質的在，那么就變成了求1到b/k和1到d/k的之間的互質的組數。

假設d大于b的話，可以從1到d枚舉i,當i小于等于b的時候，互質的數的個數就是其歐拉函數，當i大于b的時候就不是歐拉函數了,因為與i互質的

數要不大于b，那么可以逆向思維一下，求在不大于b的數中與i互質的數，這里就要用到容斥原理，

容斥原理大致是如果被計數的事物有A、B兩類，那么，A類B類元素個數總和= 屬于A類元素個數+ 屬于B類元素個數—既是A類又是B類的元素個數。

那么在這道題里就是；? 區間中與i不互質的個數 = （區間中i的每個質因數的倍數個數）-（區間中i的每兩個質因數乘積的倍數）+（區間中i的每3個質因數的成績的倍數個數）-（區間中i的每4個質因數的乘積）+~~~~~(這個容斥想了好一會兒才想通)

然后用dfs求容斥原理，看了別人代碼才看懂，還是太菜。

1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 typedef long long ll; 5 const int maxn=100010; 6 int num[maxn],p[maxn][50]; 7 ll enul[maxn]; 8 void great(){ 9 int i,j; 10 enul[1]=1; 11 for (i=2;i<maxn;i++){ 12 if (!enul[i]){ 13 for (j=i;j<maxn;j+=i){ 14 if (!enul[j]) 15 enul[j]=j; 16 enul[j]=enul[j]*(i-1)/i; 17 p[j][num[j]++]=i; 18 } 19 } 20 } 21 } 22 int dfs(int a,int b,int c){ 23 int sum=0,i; 24 for (i=a;i<num[c];i++) 25 sum+=b/p[c][i]-dfs(i+1,b/p[c][i],c); 26 return sum; 27 } 28 int main() 29 { 30 int n,a,b,c,d,k,i,t=1; 31 great(); 32 scanf("%d",&n); 33 while (n--){ 34 scanf("%d %d %d %d %d",&a,&b,&c,&d,&k); 35 if(k==0){ 36 printf("Case %d: 0\n",t++); 37 continue; 38 } 39 b=b/k;d=d/k; 40 if (b>d) swap(b,d); 41 ll ans=0; 42 for (i=1;i<=b;i++) 43 ans+=enul[i]; 44 for (i=b+1;i<=d;i++){ 45 ans+=b-dfs(0,b,i); 46 } 47 printf("Case %d: %I64d\n",t++,ans); 48 } 49 50 return 0; 51 }

?

轉載于:https://www.cnblogs.com/JJCHEHEDA/p/5267251.html

總結

以上是生活随笔為你收集整理的hdu (欧拉函数+容斥原理) GCD的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。