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=;
for(int i=;i<(<<m);i++){
int cnt=;
ll temp=;
for(int j=;j<m;j++){
if(i&(<<j)){
cnt++;
temp*=v[j];
}
}
if(cnt&)res+=n/temp;
else res-=n/temp;
}
return n-res;
} int main(){
int T;
scanf("%d",&T);
for(int cas=;cas<=T;cas++){
scanf("%I64d%I64d%I64d",&A,&B,&N);
v.clear();
for(ll i=;i*i<=N;i++){
if(N%i==){
v.push_back(i);
while(N%i==)N/=i;
}
}
if(N>)v.push_back(N);
printf("Case #%d: %I64d\n",cas,gao(B)-gao(A-));
}
return ;
}
上一篇:#英文#品读中国城市个性——秦汉雄风&和祖先在一起


下一篇:JAVA 拼接了一个sql 语句,但是最后运行报错——SQL 命令未正确结束