AcWing 890. 能被整除的数（容斥原理）

题目链接

https://www.acwing.com/problem/content/892/

思路

我们可以直接通过除法来计算每一个质数的倍数有多少个，但是这样的话可能会出现重复计算的情况，例如6是2，3的倍数，所以如果我们的n大于等于6的时候会将这个计算两次，那么我们可以通过容斥原理来计算这个整个集合的数量，我们可以通过二进制枚举或者dfs来枚举我们当前选择的集合（0个数不能算作集合，并且超过n的数也不能算在集合内）

容斥原理的思想： ∣ S 1 ∣ + ∣ S 2 ∣ + ∣ S 3 ∣ − ∣ S 1 S 2 ∣ − ∣ S 1 S 3 ∣ − ∣ S 2 S 3 ∣ + ∣ S 1 S 2 S 3 ∣ |S_1| + |S_2| + |S_3| - |S_1 S_2| - | S_1 S_3| - | S_2 S_3| + |S_1 S_2 S_3| ∣S1​∣+∣S2​∣+∣S3​∣−∣S1​S2​∣−∣S1​S3​∣−∣S2​S3​∣+∣S1​S2​S3​∣然后以此类推，如果是奇数个元素那么就是做加法，偶数个元素做减法

代码

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
//----------------自定义部分----------------
ll t,n,m,q,a[N];
void slove(){
	cin>>n>>m;
	for(int i = 0;i >a[i];
	ll ans = 0;
	for(int i = 0;i