题意
就是给出一个整数n,一个具有m个元素的数组,求出1-n中有多少个数至少能整除m数组中的一个数
(1<=n<=10^18.m<=20)
题解
这题是容斥原理基本模型。
枚举n中有多少m中元素的个数,在结合LCM考虑容斥。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const long long N=205; 8 long long a[N],n,m,ans; 9 long long gcd(long long x,long long y){10 if(y==0)return x;11 else return gcd(y,x%y);12 }13 long long lcm(long long x,long long y){14 return x/gcd(x,y)*y;15 }16 void dfs(long long now,long long num,long long res,long long k){17 if(res==0){18 if(num==0)return;19 long long tmp=n/num;20 if(k&1)ans+=tmp;21 else ans-=tmp;22 return;23 }24 if(now==m+1)return ;25 if(lcm(num,a[now])<=n)dfs(now+1,lcm(num,a[now]),res-1,k);26 dfs(now+1,num,res,k);27 }28 int main(){29 while(scanf("%lld%lld",&n,&m)!=EOF){30 n--;31 for(long long i=1;i<=m;i++)scanf("%lld",&a[i]);32 for(long long i=1;i<=m;i++)dfs(1,1,i,i);33 printf("%lld\n",ans);34 }35 }