容斥 - HDU 4135 Co-primeCo-prime Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=4135

Mean: 

給你一個區間[l,r]和一個數n，求[l,r]中有多少個數與n互素。

analyse:

經典的容斥原理題。

如果題目是說求1~n中有多少個數與n互質，我們一定反應應該是歐拉函數。

但是如果n特别大或者說是求某個給定區間與n互素的個數，這時用歐拉函數就行不通。

容斥做法：首先我們可以在O(sqrt(n))内求出n的所有質因數p1,p2,p3....pk。

對于每個質因數pi，1~r中不與它互素的個數就是r/pi。

然後就是如何容斥了？

首先我們來分析，n<=1e9，那麼n的質因數的個數最多不超過9個，那麼我們就可以對n的所有質因數進行組合來計算。

例如：30的質因數有3個(2,3,5),我們可以用二進制來表示所有的情況：

001： 5

010： 3

011： 3 5

100： 2

101： 2 5

110： 2 3

111： 2 3 5

假設有k個質因數，那麼隻需用2^k-1個數的二進制來表示即可。

剩下的就是容斥了，設cnt為1的個數(選中的質因數的個數)，當cnt為奇數，sum加上此次的;cnt為偶數，sum減去此次的。

具體看代碼。

Time complexity: O(N)

Source code: 

/*

* this code is made by crazyacking

* Verdict: Accepted

* Submission Date: 2015-08-10-19.49

* Time: 0MS

* Memory: 137KB

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#define  LL long long

#define  ULL unsigned long long

using namespace std;

LL solve(LL r,LL n)

{

     vector<LL> ve;

     LL up=(LL)sqrt(n);

     for(LL i=2;i<=up;++i)

     {

           if(n%i==0)

           {

                 ve.push_back(i);

                 while(n%i==0)

                       n/=i;

           }

     }

     if(n>1) ve.push_back(n);

     LL sum=0,si=ve.size();

     up=(1<<si)-1;

     for(LL i=1;i<=up;++i)

           LL tmp=i,bits=0,mul=1,cnt=0;

           while(tmp)

                 if(tmp&1)

                 {

                       mul*=ve[bits];

                       ++cnt;

                 }

                 ++bits;

                 tmp=tmp>>1;

           LL cur=r/mul;

           if(cnt&1) sum+=cur;

           else sum-=cur;

     return sum;

}

int main()

     ios_base::sync_with_stdio(false);

     cin.tie(0);

     LL t,cas=1;

     cin>>t;

     while(t--)

           LL l,r,n;

           cin>>l>>r>>n;

           if(l>r) swap(l,r);

           printf("Case #%lld: %lld\n",cas++,r-l+1-(solve(r,n)-solve(l-1,n)));

     return 0;