HDU 4135 Co-prime(容斥原理)

时间：2023-01-13 20:12:46

Co-prime

第一发容斥，感觉挺有意思的 →_→

【题目链接】Co-prime

【题目类型】容斥

&题意：

求(a,b)区间内，与n互质的数的个数。 \(a，b\leq 10^{15}\)

&题解：

分析：我们可以先转化下：用(1,b)区间与n互质的数的个数减去(1,a-1)区间与n互质的数的个数,那么现在就转化成求(1,m)区间于n互质的数的个数,如果要求的是(1,n)区间与n互质的数的个数的话，我们直接求出n的欧拉函数值即可，可是这里是行不通的!我们不妨换一种思路：就是求出(1,m)区间与n不互质的数的个数，假设为num，那么我们的答案就是：m-num!现在的关键就是：怎样用一种最快的方法求出(1,m)区间与n不互质的数的个数？方法实现：我们先求出n的质因子(因为任何一个数都可以分解成若干个质数相乘的),如何尽快地求出n的质因子呢？我们这里又涉及两个好的算法了!第一个：用于每次只能求出一个数的质因子,适用于题目中给的n的个数不是很多，但是n又特别大的;http://www.cnblogs.com/jiangjing/archive/2013/06/03/3115399.html 第二个：一次求出1~n的所有数的质因子,适用于题目中给的n个数比较多的，但是n不是很大的。 http://www.cnblogs.com/jiangjing/archive/2013/06/01/3112035.html 本题适用第一个算法！举一组实例吧:假设m=12,n=30.

第一步：求出n的质因子：2,3,5；

第二步：(1,m)中是n的因子的倍数当然就不互质了(2,4,6,8,10)->n/2 6个,(3,6,9,12)->n/3 4个,(5,10)->n/5 2个。

如果是粗心的同学就把它们全部加起来就是：6+4+2=12个了，那你就大错特错了,里面明显出现了重复的,我们现在要处理的就是如何去掉那些重复的了！

第三步：这里就需要用到容斥原理了，公式就是：n/2+n/3+n/5-n/(2* 3)-n/(2* 5)-n/(3* 5)+n/(2* 3* 5).

第四步:我们该如何实现呢？我在网上看到有几种实现方法：dfs(深搜)，队列数组，位运算三种方法都可以！上述公式有一个特点：n除以奇数个数相乘的时候是加，n除以偶数个数相乘的时候是减。我这里就写下用队列数组如何实现吧：我们可以把第一个元素设为-1然后具体看代码如何实现吧！

【时间复杂度】O(\(\sqrt{n}\))

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))

#define rep(i,b) for(int i=0;i<(b);i++)

#define rez(i,a,b) for(int i=(a);i<=(b);i++)

#define red(i,a,b) for(int i=(a);i>=(b);i--)

const ll LINF = 0x3f3f3f3f3f3f3f3f;

#define PU(x) puts(#x);

#define PI(A) cout<<(A)<<endl;

#define DG(x) cout<<#x<<"="<<(x)<<endl;

#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;

#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS = 1e-9 ;

/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */

const int MAXN = 10000 + 9 ;

ll a,b,n,phi[MAXN],num;

int K;

void pre(ll n){

    ll i;

    num=0;

    for(i=2;i*i<=n;i++){

        if (n%i==0){

            phi[num++]=i;

            while(n%i==0) n/=i;

        }

    }

    if (n>1) phi[num++]=n;

}

ll pie(ll m){

    ll que[MAXN],i,j,k,t=0,sum=0;

    que[t++]=-1;

    for(i=0;i<num;i++){

        k=t;

        for(j=0;j<k;j++)

            que[t++]=que[j]*phi[i]*(-1);

    }

    for(i=1;i<t;i++){

        sum+=m/que[i];

    }

    return sum;

}

void Solve()

{

    scanf("%lld%lld%lld",&a,&b,&n);

    pre(n);

    ll ans=b-pie(b)-(a-1-pie(a-1));

    printf("Case #%d: %lld\n",++K,ans);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("1.in", "r", stdin);

    freopen("1.out","w",stdout);

#endif

//iostream::sync_with_stdio(false);

//cin.tie(0), cout.tie(0);

    int T;cin>>T;while(T--)

    Solve();

    return 0;

}

转载自： http://www.cnblogs.com/jiangjing/archive/2013/06/03/3115470.html

相关文章