hdu 1695 GCD (素數篩選 + 歐拉函數 + 容斥原理)

http://acm.hdu.edu.cn/showproblem.php?pid=1695

題意：求 1~b  和 1~ d  有 多少對 數 的 gcd（x，y） = k ？

       x = 5  y=7 和 x= 7,y = 5 被認為是 同一種。

題解：

如果兩個數的 最大 公約數  是  k 的 話 ，那麼  x/k  與  y /k  是 互質的。

是以 原題 可以轉化為  求  1~b/k   和 1~d/k  有 多少對 互質的 數。

假設 b = b/k，d= d/k　，b<ｄ

1：對于　　1~b 我們可以 利用 歐拉函數 求 其 歐拉函數值 。

歐拉函數是指：對于一個正整數n，小于n且和n互質的正整數的個數，記做：φ(n)，其中φ(1)被定義為1，但是并沒有任何實質的意義

定義小于n且和n互質的數構成的集合為Zn，稱呼這個集合為n的完全餘數集合。

顯然，對于素數p，φ(p)= p -1.對于兩個素數p、q，他們的乘積n = pq 滿足φ(n) =(p-1)(q-1)

         證明：對于質數p,q，滿足φ(n) =(p-1)(q-1)

         考慮n的完全餘數集Zn = { 1,2,....,pq -1}

         而不和n互質的集合由下面三個集合的并構成：

         1) 能夠被p整除的集合{p,2p,3p,....,(q-1)p} 共計q-1個

         2) 能夠被q整除的集合{q,2q,3q,....,(p-1)q} 共計p-1個

         3) {0}

         很顯然，1、2集合中沒有共同的元素，是以Zn中元素個數 ＝ pq - (p-1 + q- 1 + 1) = (p-1)(q-1)

         上式中黑體的1是它本身，因為是小于它且和它互質的數，是以當然必須減去自身了。

歐拉函數的定義:E(k)=([1,n-1]中與n互質的整數個數).因為任意正整數都可以唯一表示成如下形式:

k=p1^a1*p2^a2*……*pi^ai;(即分解質因數形式)

可以推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))

               =k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);

               =k*(1-1/p1)*(1-1/p2)....(1-1/pk)

 2：  對于  大于 b 的 我門可以 利用  容斥原理 求出 。

  1 #include<cstdio>

  2 #include<cstring>

  3 #include<cmath>

  4 #include<iostream>

  5 #include<algorithm>

  6 #include< set>

  7 #include<map>

  8 #include<queue>

  9 #include<vector>

 10 #include< string>

 11  #define inf 0x7fffffff

 12  #define maxn 160000

 13  #define CL(a,b) memset(a,b,sizeof(a))

 14  #define  ll  long long

 15  #define mx 100010

 16  using  namespace std;

 17 

 18 

 19  bool f[maxn] ;

 20 ll phi[maxn] ; // 記錄歐拉函數值

 21  ll prim[maxn] ;

 22 vector<ll>g[maxn];

 23  void init() //  素數篩選 及求 歐拉函數值

 24  {

 25     ll num =  0 ,i,j;

 26 

 27     phi[ 1] =  1 ;

 28 

 29     CL(f, false) ;

 30 

 31      for(i =  2 ; i <=  100000;i++)

 32     {

 33 

 34          if(f[i] ==  false)

 35         {

 36             prim[num++] = i;

 37             phi[i] = i -  1 ;

 38         }

 39          for(j =  0;j< num&&prim[j]*i <=  100000;j++)

 40         {

 41               f[i*prim[j]] =  true ;

 42                if(i%prim[j] ==  0)

 43               {

 44                   phi[i*prim[j]] = phi[i] *prim[j] ;

 45 

 46               }

 47                else

 48                  phi[i*prim[j]] = phi[i]*(prim[j] -  1) ;

 49 

 50         }

 51     }

 52 

 53 

 54 

 55      for(ll x =  1 ; x <=  100000;x++) // 找出所有數的 質因子

 56      {

 57 

 58         ll tmp = x;

 59         for(i =  0 ;prim[i] *prim[i] <= tmp ;i++)

 60        {

 61             if(tmp % prim[i] ==  0)

 62            {

 63                g[x].push_back(prim[i]) ;

 64 

 65                 while(tmp%prim[i] ==  0)tmp/=prim[i] ;

 66            }

 67 

 68 

 69             if(tmp ==  1)  break ;

 70        }

 71 

 72        if(tmp >  1)g[x].push_back(tmp) ;

 73     }

 74 }

 75 

 76 

 77 ll dfs(ll x,ll b,ll now) // 容斥原理

 78  {

 79     ll  res  =  0  ;

 80     ll i =  0 ;

 81      for(i = x; i < g[now].size();i++ )

 82        res = res + b/g[now][i] - dfs(i+ 1,b/g[now][i],now) ;

 83 

 84     return res ;

 85 }

 86  int main()

 87 {

 88      int T ,i;

 89     init() ;

 90     scanf( " %d ",&T);

 91      int cas =  0 ;

 92     ll a,b,c,d ,k;

 93      while(T--)

 94     {

 95         scanf( " %I64d%I64d%I64d%I64d%I64d ",&a,&b,&c,&d,&k) ;

 96 

 97          if(b > d ) swap(b,d) ;

 98 

 99          if(k ==  0|| k>b||k>d)

100         {

101             printf( " Case %d: 0\n ",++cas);

102              continue ;

103         }

104 

105         b = b/k ;

106         d = d/k  ;

107         ll ans =  0 ;

108          for(i =  1; i <= b;i++)

109            ans+=phi[i] ;

110          for(i = b+ 1; i <= d;i++)

111         {

112 

113             ans=ans + b - dfs( 0,b,i);

114 

115         }

116 

117 

118         printf( " Case %d: %I64d\n ",++cas,ans) ;

119 

120 

121 

122     }

123 

124 }

轉載于:https://www.cnblogs.com/acSzz/archive/2012/11/24/2785499.html