hdu 5135 Co-prime（求m以内与n互质的个数）

本文主要是介绍hdu 5135 Co-prime（求m以内与n互质的个数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4135
如果是求某一个n互质的个数的话，那确实是这样容斥比较好
原理也感觉比较简单，要找与n互质那就是要找，那就减去不互质的个数不就行了，于是就把n的质因子找出来，那么质因子的倍数就肯定与n不互质，然后就容斥。

容斥有dfs，和位运算枚举出来，而今天学到了一个直接用队列数组容斥出来的，哇感觉很爽~
参考这位大佬的博客：https://www.cnblogs.com/jiangjing/archive/2013/06/03/3115470.html

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
LL L,R,N;
int t;
int prime[maxn];
int que[maxn];
LL solve(LL n)//求n以内与N不互质的个数 
{LL ans=0;for(int i=2; i<=t; i++){ans+=n/que[i];}return ans;
}
int main()
{int T;cin>>T;for(int Case=1; Case<=T; Case++){cin>>L>>R>>N;LL n=N;int cnt=0;for(LL i=2; i*i<=n; i++){if(n%i==0){while(n%i==0)n/=i;prime[++cnt]=i;}}if(n>1)prime[++cnt]=n;t=0;que[++t]=-1;for(int i=1; i<=cnt; i++)//用队列数组进行容斥 {int len=t;for(int k=1; k<=len; k++)que[++t]=que[k]*prime[i]*(-1);}cout<<"Case #"<<Case<<": "<<R-L+1-(solve(R)-solve(L-1))<<endl;}
}

这篇关于hdu 5135 Co-prime（求m以内与n互质的个数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---