解法一
二进制枚举
#include <bits/stdc++.h> using namespace std; typedef long long ll; int a[25]; ll sum,l,r,k; int main() { cin>>l>>r>>k; l--; for(int i=0;i<k;i++) scanf("%d",&a[i]); for(int i=1;i<(1<<k);i++){ //对1左移k位,对每个数是否被选中进行二进制枚举 ll t=1,cnt=0; for(int j=0;j<k;j++){ if(i&(1<<j)){ //判断第i个数是否被选中 cnt++; //共计被选中了n个数 t*=a[j]; //被选中的数的最小公倍数为t(A中元素都是素数) if(t>r) break; } } if(cnt&1) sum+=r/t-l/t; //右容斥原理可知当所选数子个数为奇数时相加,为偶数时相减(由容斥原理可知奇数相加偶数相减) else sum-=r/t-l/t; } cout<<r-l-sum; }
解法二
递归
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a1[25]; ll l,r,k; ll solve(ll a,ll b){ //对a1的第a位的数是否被选中来进行a1递归,通过b不除以a1的第a位减去b除以a1的第a位来计算b对a1中任意几位的最小公倍数的除数(就像上一种解法中奇数加,偶数减一样) if(a==k) return b; else return solve(a+1,b)-solve(a+1,b/a1[a]); } int main() { cin>>l>>r>>k; for(int i=0;i<k;i++) scanf("%d",&a1[i]); cout<<solve(0,r)-solve(0,l-1)<<endl; }