挺神的一道题 ~
由于两个人选的数字不能有互质的情况，所以说对于一个质因子来说，如果 1 选了，则 2 不能选任何整除该质因子的数.
然后，我们发现对于 1 ~ 500 的数字来说，只可能有一个大于 $\sqrt 500$ 的质因子（两个的话乘积就超过 500 了）
而不大于 $\sqrt 500$ 的质因子总数只有 8 个，所以可以对这 8 个质因子状压.
我们先假设所有数字都 $\eqslant 30$，即所有质因子都 $leqslant \sqrt 500$.
定义状态 dp[i][j] 表示第一个人选的质因子集合为 $i$，第二个人选的质因子集合为 $j$.
那么直接更新 $dp[i|sta][j]+=dp[i][j]$ (sta 与 k 无交集）
对于第二个维度同理.
由于我们用滚动数组，所以还要定义 f1[i][j], f2[i][j] 表示第一个人/第二个人 和 第二个人/第一个人 状态下的方案数.
这个转移弄完之后，我们再考虑加入大于 $\sqrt 500$ 的质因子的情况：
令这个质因子为 $x$，那么会有一段数字都包含这个 $x$，显然这些数中只能让 1 个人去选择这个质因子.
我们沿用上面那个 f1[i][j], f2[i][j] 来更新，然后对于这一段的开始位置直接令 f1=f2=dp，其余的正常 dp。
处理完这段的时候还要减去两个数都不选的情况.
最后 dp'[i][j]=f1[i][j]+f2[i][j]-dp[i][j].
code:
#include <bits/stdc++.h>
#define N 703
#define LL long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n;
int poww[N];
LL ans,mod;
LL dp[N][N],f1[N][N],f2[N][N];
int p[13]={0,2,3,5,7,11,13,17,19,23};
struct data
{
int num,bi,sta;
}a[N];
bool cmp(data a,data b)
{
return a.bi<b.bi;
}
void init(int num)
{
int i,j,v=num,bi=0;
for(i=1;i<=8;++i)
{
if(v%p[i]==0)
{
a[num].sta|=poww[i];
while(v%p[i]==0) v/=p[i];
}
}
if(v>1) bi=v;
a[num].bi=bi;
a[num].num=num;
}
int main()
{
// setIO("input");
int i,j;
scanf("%d%lld",&n,&mod);
for(i=1;i<=12;++i) poww[i]=(1<<(i-1));
for(i=2;i<=n;++i) init(i);
sort(a+2,a+1+n,cmp);
dp[0][0]=1ll;
for(i=2;i<=n;++i)
{
if(i==2||!a[i].bi||a[i].bi!=a[i-1].bi)
{
memcpy(f1,dp,sizeof(dp));
memcpy(f2,dp,sizeof(dp));
}
for(j=255;j>=0;--j)
{
for(int k=255;k>=0;--k)
{
if((j&a[i].sta)==0) f1[j][k|a[i].sta]=(f1[j][k|a[i].sta]+f1[j][k])%mod;
if((k&a[i].sta)==0) f2[j|a[i].sta][k]=(f2[j|a[i].sta][k]+f2[j][k])%mod;
}
}
if(i==n||!a[i].bi||a[i].bi!=a[i+1].bi)
{
for(j=0;j<=255;++j)
{
for(int k=0;k<=255;++k)
{
dp[j][k]=(f1[j][k]+f2[j][k]-dp[j][k]+mod)%mod;
}
}
}
}
LL ans=0ll;
for(i=0;i<=255;++i) for(j=0;j<=255;++j) if((i&j)==0) (ans+=dp[i][j])%=mod;
printf("%lld\n",ans);
return 0;
}