原文链接www.cnblogs.com/zhouzhendong/p/UOJ129.html
题解
考虑把大于等于 $\sqrt n$ 的质数和小于 $\sqrt n$ 的分开考虑：
1. 小于等于 $\sqrt n$ 的质数最多只有 8 个。
2. 一个小于等于 n 的正整数最多包含 1 个 大于 $\sqrt n$ 的质因子，所以不同的这种质因子可以分离。
考虑对双方掌控了哪些小于等于 $\sqrt n$ 的质数进行状压，然后按照除去小于等于 $\sqrt n$ 的因子后的值，将所有数分成若干类，考虑对同一类不同时出现在两个人手上的方案数进行 DP 即可。
时间复杂度 $O(3 ^ 8 \cdot n )$ 。
代码
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=a;i<=b;i++)
#define Fod(i,b,a) for (int i=b;i>=a;i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define real __zzd001
#define _SEED_ ('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')
#define outval(x) printf(#x" = %d\n",x)
#define outvec(x) printf("vec "#x" = ");for (auto _v : x)printf("%d ",_v);puts("")
#define outtag(x) puts("----------"#x"----------")
#define outarr(a,L,R) printf(#a"[%d...%d] = ",L,R);\For(_v2,L,R)printf("%d ",a[_v2]);puts("");
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> vi;
LL read(){LL x=0,f=0;char ch=getchar();while (!isdigit(ch))f|=ch=='-',ch=getchar();while (isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return f?-x:x;
}
const int N=505;
int n,mod;
void Add(int &x,int y){if ((x+=y)>=mod)x-=mod;
}
void Del(int &x,int y){if ((x-=y)<0)x+=mod;
}
int dp[2][1<<9][1<<9];
int p[8]={2,3,5,7,11,13,17,19};
int a[N],val[N],sit[N];
bool cmp(int a,int b){return val[a]<val[b];
}
int main(){n=read(),mod=read();For(i,2,n){a[i]=i;val[i]=i,sit[i]=0;For(j,0,7)if (val[i]%p[j]==0){sit[i]|=1<<j;while (val[i]%p[j]==0)val[i]/=p[j];}if (val[i]!=1)sit[i]|=1<<8;}sort(a+2,a+n+1,cmp);dp[0][0][0]=1;For(id,2,n){int v=a[id],s=sit[v];int T0=id&1,T1=T0^1;For(i,0,511){int ii=i^511;for (int j=ii;j>=0;j=(j-1)&ii){dp[T1][i][j]=0;if (!j)break;}}if (val[v]!=val[a[id-1]]){For(i,0,511){int ii=i^511;for (int j=ii;j>=0;j=(j-1)&ii){if (dp[T0][i][j]){if (i>>8){Add(dp[T0][i^1<<8][j],dp[T0][i][j]);dp[T0][i][j]=0;}else if (j>>8){Add(dp[T0][i][j^1<<8],dp[T0][i][j]);dp[T0][i][j]=0;}}if (!j)break;}}}For(i,0,511){int ii=i^511;for (int j=ii;j>=0;j=(j-1)&ii){if (dp[T0][i][j]){Add(dp[T1][i][j],dp[T0][i][j]);if (!(i&s))Add(dp[T1][i][j|s],dp[T0][i][j]);if (!(j&s))Add(dp[T1][i|s][j],dp[T0][i][j]);}if (!j)break;}}}int ans=0;For(i,0,511)For(j,0,511)Add(ans,dp[(n&1)^1][i][j]);cout<<ans<<endl;return 0;
}