首页 > 代码库 > HDU 4135
HDU 4135
http://acm.hdu.edu.cn/showproblem.php?pid=4135
求[A,B]内与N互素的数字个数
首先对N分解质因数,对于一个质因数,1-n与它不互素的数字个数是n/(这个质因数),这样可以得到m个集合(m是N分解出的质因数的个数),对这m个集合用容斥原理解出来它们的并集,再用总数去减
这里学习了用位运算求解容斥原理,非常简单,和状压dp中的位运算差不多感觉,注意容斥中奇加偶减
#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;typedef __int64 ll;ll A,B,N;vector <ll> v;ll gao(ll n){ int m=v.size(); ll res=0; for(int i=1;i<(1<<m);i++){ int cnt=0; ll temp=1; for(int j=0;j<m;j++){ if(i&(1<<j)){ cnt++; temp*=v[j]; } } if(cnt&1)res+=n/temp; else res-=n/temp; } return n-res;}int main(){ int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++){ scanf("%I64d%I64d%I64d",&A,&B,&N); v.clear(); for(ll i=2;i*i<=N;i++){ if(N%i==0){ v.push_back(i); while(N%i==0)N/=i; } } if(N>1)v.push_back(N); printf("Case #%d: %I64d\n",cas,gao(B)-gao(A-1)); } return 0;}
HDU 4135
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。