题目概述

把 $[2,n]$ 分成两半（不需要全部选），求两边不存在不互质的数的方案数。

解题报告

如果素数个数少的话可以直接状压 $f_{s,t}$ 表示第一组的素数集合为 $s$ ，第二组的素数集合为 $t$ 的方案数，只要 $s\ and\ t=0$ 说明合法。

但是素数个数多的时候就炸了，不过我们发现每个数 $>\sqrt n$ 的质因子最多只有一个。先预处理每个数 $i$ 的最大质因数，如果最大质因数 $>\sqrt n$ 我们就暴力讨论这些数放在哪边，这样剩下 $\le \sqrt n$ 的素数只有 $8$ 个，可以直接状压。

那么按照最大质因数排序，对于最大质因数( $>\sqrt n$ )相同的这些数，我们放在一起做，定义 $g_{0/1,s,t}$ 表示这些数放在第一组/第二组，$\le \sqrt n$ 的素数状态为 $s,t$ 的方案数。刚开始 $g_{0,s,t}=g_{1,s,t}=f_{s,t}$ 即之前的答案，然后用这些数进行DP，最后修正 $f_{s,t}=g_{0,s,t}+g_{1,s,t}-f'_{s,t}$ ，减去原来的 $f'_{s,t}$ 是因为没选的方案算了两次。

示例程序

#include<cmath>
#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
using namespace std;
const int maxn=500,maxk=8,maxs=1<<maxk;

int n,S,MOD,p[maxn+5];bool pri[maxn+5];pair<int,int> a[maxn+5];
int f[maxs][maxs],g[2][maxs][maxs],ans;

inline void Make(int n){
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=n;j++)
            {pri[t]=true;if (!(i%p[j])) break;}
    }
}
#define ADD(x,y) (((x)+(y))%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&MOD);Make(n);
    for (int i=2;i<=n;i++)
        for (int j=(a[i].fr=n+i,1);j<=p[0];j++)
            if (!(i%p[j])) if (p[j]<=19) a[i].sc|=1<<j-1; else a[i].fr=p[j];
    sort(a+2,a+1+n);f[0][0]=1;
    for (int i=2,j;i<=n;i=j){
        for (int s=0;s<maxs;s++)
            for (int t=0;t<maxs;t++)
                g[0][s][t]=g[1][s][t]=f[s][t];
        for (j=i;j<=n&&a[i].fr==a[j].fr;j++)
            for (int s=maxs-1;~s;s--)
                for (int t=maxs-1;~t;t--){
                    if (g[0][s][t]) g[0][s|a[j].sc][t]=ADD(g[0][s|a[j].sc][t],g[0][s][t]);
                    if (g[1][s][t]) g[1][s][t|a[j].sc]=ADD(g[1][s][t|a[j].sc],g[1][s][t]);
                }
        for (int s=0;s<maxs;s++)
            for (int t=0;t<maxs;t++)
                if (!(s&t)) f[s][t]=ADD(ADD(g[0][s][t],g[1][s][t]),MOD-f[s][t]);
    }
    for (int s=0;s<maxs;s++) for (int t=0;t<maxs;t++) ans=ADD(ans,f[s][t]);
    printf("%d\n",ans);return 0;
}