P5539题解
题目描述
小 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 求出来。
题解
首先，看一眼感觉是中国剩余定理。但是复杂度是有问题的。
考虑到 \(abc\) 很大时可以暴力求解，想到套路性的bitset优化暴力。
我们用unsigned long long手写bitset来维护 \(n\) 个数。对于一个数 \(x\in S\)。当 \(x>64\) 时。显然可以直接暴力求解。反之我们用类似于分块的思想，先处理出1~64个 \(x\) 的结果，因为每 \(x\) 为一循环,一个ull又维护64位。因此就构成了一个完整的循环结，再暴力求解即可。
观察到答案只与数有关，统计连续的 \(1\) 即可。
代码：
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull bs[15625009],cs[70];
int n,m;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
if(x>64)
{
for(int j=0;j<=n;j+=x)
bs[j/64]|=(1ull<<(j%64));
}
else
{
for(int j=0;j<=x;j++)
cs[j]=0;
for(int j=0;j<=64;j++)
cs[j*x/64]|=(1ull<<(j*x%64));
for(int j=0;j<=n/64;j++)
bs[j]|=cs[j%x];
}
}
for(int i=n+1;i/64==n/64;i++)
bs[i/64]=((bs[i/64]|(1ull<<(i%64)))^(1ull<<(i%64)));
bs[0]=((bs[0]|1)^1);
int ans=0;
for(int i=0;i<=n/64;i++)
{
ull f=bs[i];
f=f&(f>>1)&(f>>2);
while(f)ans+=(f&1),f>>=1;
}
for(int i=1;i<=n/64;i++)
{
if((bs[i]&1)&&(bs[i-1]&(1ull<<63))&&(bs[i-1]&(1ull<<62)))
ans++;
if((bs[i]&1)&&(bs[i]&2)&&(bs[i-1]&(1ull<<63)))
ans++;
}
cout<<ans;
return 0;
}