自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:11:48，当前版本为作者最后更新于2019-09-24 22:25:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人怎么一直不发题解啊，，
那我就来水一篇好了（

首先，这题看起来时什么 $\Theta(2^{|S|})$ 之类的做法，然而实际上就是 $\Theta(n|S|/w)$ 的 bitset 大暴力。

做法也就是开一个 $10^9$ 的数组，对于 $S$ 中的每个数 $k$，把 $k$ 的倍数都设为 $1$，统计数组中有多少组 $3$ 个连续的 $1$ 即是答案。

然后把这个过程用 bitset 优化一下就可以了（
另外要注意的一点，$x$ 是正整数，或许要把第 $0$ 项的贡献判掉

ps：这个东西和分块的思想很像，不过是基于CPU的运算优化的。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1000000003
#define reg register
using namespace std;

unsigned long long bs[(N>>6)+10];
unsigned long long tmp[65];
int n,m,s,l,ans;

inline int count(unsigned long long x){
    reg int res = 0;
    while(x){
        res += x&1;
        x >>= 1;
    }
    return res;
}

int main(){
    scanf("%d%d",&n,&s);
    m = (n>>6)+1;
    while(s--){
        scanf("%d",&l);
        if(l<64){ //两种情况判一下,保证加入的复杂度是 n/w
            memset(tmp,0,sizeof(tmp));
            for(reg int i=0;i<(l<<6);i+=l)
                tmp[i>>6] |= 1ull<<(i&63); //加入的数比较小,开另一个数组,作为重复单元
            for(reg int i=0;i<=m;i+=l)
            for(reg int j=0;j<l;++j)
                bs[i+j] |= tmp[j];    
        }else{
            for(reg 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; //除去第 0 项
    for(reg int i=0;i<=m;++i) ans += count(bs[i]&(bs[i]<<1)&(bs[i]<<2));
    for(reg int i=1;i<=m;++i) ans += count(bs[i]&(bs[i-1]>>62)&((bs[i-1]>>63)|(bs[i]<<1)));
    printf("%d",ans);
    return 0;
}