题目大意

有两个集合\(S_1,S_2 \subseteq [2,n] (n\leq 500)\)，且对于\(\forall x\in S_1,y\in S_2 , gcd(x,y)=1\)
求\(S_1,S_2\)有多少种方案
两种方案不同，当且仅当 方案一的\(S_1\)与方案二的\(S_1\)存在一个元素不同 或 方案一的\(S_2\)与方案二的\(S_2\)存在一个元素不同

题解

当\(n\leq 100\)时，设\(f(A_1,A_2)\)表示当\(S_1\)中所有数的质因子集合为\(A_1\)，\(S_2\)中所有数的质因子集合为\(A_2\)时的方案数，枚举2到\(n\)的每个数放到哪个集合里，直接dp
当\(n\leq 500\)时，发现对于每个大于\(\sqrt{n}\)的质数，它作为质因子时的幂次数不超过一
那么对于每个大于\(\sqrt{n}\)的质数，枚举包含它的所有数都被分到\(S_1\)还是\(S_2\)，设\(g(i,A_1,A_2)\)表示当包含当前枚举的这个质因数的数都在\(S_i\)里，\(S_1\)中所有数的质因子集合为\(A_1\)，\(S_2\)中所有数的质因子集合为\(A_2\)时的方案数，还是直接dp

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define maxn 510
#define maxs ((1<<8)+7)
#define LL long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    if(x==0){putchar('0'),putchar('\n');return;}
    int f=0;char ch[20];
    if(x<0)putchar('-'),x=-x;
    while(x)ch[++f]=x%10+'0',x/=10;
    while(f)putchar(ch[f--]);
    putchar('\n');
    return;
}
int n,mod,no[maxn],p[maxn],cntp,bul[maxn][maxn],son[maxn],f[maxs][maxs],f1[maxs][maxs],vis[maxn],f2[maxs][maxs];
signed main()
{
    n=read(),mod=read();
    rep(i,2,n)
        if(!no[i])
        {
            p[++cntp]=i;
            for(int j=i+i;j<=n;j+=i)no[j]=1;    
        }
    rep(i,2,n)
    {
        int lim=min(8,cntp);
        rep(j,1,lim)if(i%p[j]==0)son[i]|=(1<<(j-1));
        int f=8;
        for(int j=9;j<=cntp&&p[j]<=i;j++)if(i%p[j]==0){f=j;break;}
        bul[f][++bul[f][0]]=i;
    }
    int fulls=(1<<8)-1;f[0][0]=1;
    rep(j,1,bul[8][0])
    {
        int num=bul[8][j];
        dwn(s1,fulls,0)
            dwn(s2,fulls,0)
            {
                if(!(son[num]&s2))(f[s1|son[num]][s2]+=f[s1][s2])%=mod;
                if(!(son[num]&s1))(f[s1][s2|son[num]]+=f[s1][s2])%=mod;
            }
    }
    rep(i,9,cntp)
    {
        if(bul[i][0])memcpy(f1,f,sizeof(f)),memcpy(f2,f,sizeof(f));
        rep(j,1,bul[i][0])
        {
            int num=bul[i][j];
            dwn(s1,fulls,0)
                dwn(s2,fulls,0)
                {
                    if(!(son[num]&s2))(f1[s1|son[num]][s2]+=f1[s1][s2])%=mod;
                    if(!(son[num]&s1))(f2[s1][s2|son[num]]+=f2[s1][s2])%=mod;
                }
        }
        if(bul[i][0])rep(s1,0,fulls)rep(s2,0,fulls)f[s1][s2]=((f1[s1][s2]+f2[s1][s2]-f[s1][s2])%mod+mod)%mod;//既不放1号集合也不放2号集合的情况算重复了，要减去
    }
    int ans=0;
    rep(s1,0,fulls)rep(s2,0,fulls)(ans+=f[s1][s2])%=mod;
    write(ans);
    return 0;
}