夏晓光(loveJY)的博客

EI强力推荐神题

小 X 得到了一个正整数 $n$ 和一个正整数集合 $S$，他想知道有多少个正整数 $x$ 满足以下所有条件：

• $3 \le x \le n$
• 存在 $a \in S, x \equiv 0 \pmod a$
• 存在 $b \in S,x-1 \equiv 0 \pmod b$
• 存在 $c \in S,x-2 \equiv 0 \pmod c$

请你帮小 X 求出来。

$n<=1e9,|S|<=20$

你发现我竟然贴出了数据范围,说明这个题一定不一般

你想$2^|S|$?其实出题人挺坏的,如果他开到|S|=21你就不会这样想了?

复杂度其实是$O(n|S|/\omega)$啊,这罪恶的欧米伽

古有$n^2$过十万,今有我$1e9*20$随便跑

bitset优化其实不简单,因为是基于cpu去优化的,所以理论上不行但实际上cpu使劲跑是可以的

做法也很简单,开个1e9,然后考虑把每个S中的数的倍数设置为1,那么答案就是有多少个连续三个1

统计答案怎么bitset?

如果在同一个w内,直接bs&bs>>1&bs>>2

如果跨过一个w,可以把$bs_i$有两个$bs_{i-1}$有1个算在$bs_i$的第二个

而$bs_i$有一个的那种就记在$bs_i$第一个位置

具体我们需要手写bitset,然后看代码吧

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#define ull unsigned long long
const int MAXN = 1e9 + 7;
using namespace std;
ull bs[(MAXN >> 6) + 10];//就硬开啊qwq
ull tmp[65];
int n, m, s, l, ans;

inline int count(ull x) {
	return __builtin_popcountll(x);
}

int main() {
	scanf("%d%d", &n, &s);
	m = (n >> 6) + 1;
	while(s--) {
		scanf("%d", &l);
		if(l < 64) {
			memset(tmp, 0, sizeof(tmp));
			for(register int i = 0; i < (l << 6); i += l)tmp[i >> 6] |= 1ull << (i & 63);//这个可以考虑把这个数暴力倍增直到大小大于w
			for(register int i = 0; i <= m; i += l)
				for(register int j = 0; j < l; ++j)bs[i + j] |= tmp[j];//同时处理w大小的

		} else {
			for(register int i = 0; i <= n; i += l) {
				bs[i >> 6] |= 1ull << (i & 63);//这个可以直接加
			}
		}
	}
	--m;
	if((n & 63) != 63)bs[m] &= (1ull << (n + 1 - (m << 6))) - 1;
	bs[0] &= -2ull;//超过边界的1搞掉
	for(register int i = 0; i <= m; ++i)ans += count(bs[i] & (bs[i] << 1) & (bs[i] << 2));//考虑一个w内连续的3这样一定计算一次
	for(register int i = 1; i <= m; ++i)ans += count(bs[i] & (bs[i - 1] >> 62) & ((bs[i - 1] >> 63) | (bs[i] << 1)));//考虑跨过w的3连
	printf("%d\n", ans);
	return 0;
}

$qwq$