AcWing 890. 能被整除的数
原题链接
简单
作者:
lwt_3
,
2023-02-10 19:34:51
,
所有人可见
,
阅读 140
DFS深搜版
#include<iostream>
using namespace std;
const int N=20;
double st[N];
int n,m;
int primes[N],cnt;
void count(int s,int k,int tmp){
if(k==s) {
double res=n;
for(int i=0;i<s;i++) res/=st[i];
if(s%2) cnt+=(int)res;
else cnt-=(int)res;
return;
}
for(int i=tmp+1;i<m;i++){
if(i+s-k>m) break;
st[k++]=primes[i];
count(s,k,i);
k--;
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++) cin>>primes[i];
for(int i=1;i<=m;i++) count(i,0,-1);
cout<<cnt;
return 0;
}
位运算版
#include<iostream>
using namespace std;
const int N=20;
double st[N];//所选质数的集合
int n,m;
int primes[N],cnt;
void count(int s,int k,int tmp){//s表示需选质数个数,K表示当前已选择质数个数,tmp表示当前指针
if(k==s) {
double res=n;
for(int i=0;i<s;i++) res/=st[i];
if(s%2) cnt+=(int)res;
else cnt-=(int)res;
return;
}
for(int i=tmp+1;i<m;i++){
if(i+s-k>m) break;
st[k++]=primes[i];
count(s,k,i);
k--;
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++) cin>>primes[i];
for(int i=1;i<=m;i++) count(i,0,-1);
cout<<cnt;
return 0;
}