算法1

(手写biset) $O(n*s/w)$

首先，这题看起来是 Θ(2^|S|) 之类的做法，然而实际上就是 Θ(n|S|/w) 的 bitset 大暴力。

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

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

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

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
const int N=1e9+3;
ULL bs[(N>>6)+10];
ULL tmp[65];
int n,m,s,l,ans;
int count(ULL x)
{
    int res=0;
    while(x)
    {
        res+=x&1;
        x>>=1;
    }
    return res;
}
int main()
{
    cin>>n>>s;
    m=(n>>6)+1;
    while(s--)
    {
        scanf("%d",&l);
        if(l<64)  //两种情况判一下,保证加入的复杂度是 n/w
        {
            memset(tmp,0,sizeof tmp);
            for(int i=0;i<(l<<6);i+=l)tmp[i>>6]|=1ull<<(i&63);  //加入的数比较小,开另一个数组,作为重复单元
            for(int i=0;i<=m;i+=l)
                for(int j=0;j<l;j++)
                    bs[i+j]|=tmp[j];
        }
        else
        {
            for(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(int i=0;i<=m;i++)ans+=count(bs[i]&(bs[i]<<1)&(bs[i]<<2));
    for(int i=1;i<=m;i++)ans+=count(bs[i]&(bs[i-1]>>62)&((bs[i-1]>>63)|(bs[i]<<1)));
    printf("%d\n",ans);
    return 0;
}