艺术网站欣赏/网站排名优化工具

A

题意：
给你一个集合a,里面都是素数，现在问你l到r区间内有多少个数和集合a无关，无关的条件是不能为里面元素任意一个的倍数。

总结：
如果直接做不好做，看到l和r非常大，但是集合a不大，所以可以dfs去容斥答案，当然也可以二进制枚举当前的数是哪些数的倍数，然后再减去就行了。

代码：

二进制枚举：int T,n,m,k;
int va[N];signed main()
{IOS;int a,b;cin>>a>>b>>n;int ans = b-a+1;for(int i=1;i<=n;i++) cin>>va[i];for(int i=1;i<(1ll<<n);i++){int l = a-1,r = b,cnt = 0;for(int j=0;j<n;j++){if(i>>j&1){cnt++;l /= va[j+1];r /= va[j+1];}}if(cnt&1) ans -= r-l;else ans += r-l;}cout<<ans;return 0;
}dfs:int T,n,m,k;
int va[N];int f(int now,int x)
{if(now>n) return x;else return f(now+1,x)-f(now+1,x/va[now]);
}signed main()
{IOS;int a,b;cin>>a>>b>>n;for(int i=1;i<=n;i++) cin>>va[i];cout<<f(1,b)-f(1,a-1);return 0;
}

总结：
多多积累经验呀。