题面
思路
首先，要让两个人选的数字全部互质，那么有一个显然的充要条件：甲选的数字的质因数集合和乙选的数字的质因数集合没有交集
30pt
这种情况下n<=30，也就是说可用的质数只有10个，我们可以开个状压搞一搞
设$dp[S_1][S_2]$表示甲选择的质因数集合是$S_1$，乙是$S_2$的总情况数，
对于每个2-n分解质因数，把每个质因数是否出现状压起来存下来，dp的时候从前往后扫
那么可以刷表法做一波$dp[i][S_1|k][S_2]+=dp[i-1][S_1][S_2]$$(k$ $bitand$ $S_2=0)$，或者$dp[i][S_1][S_2|k]+=dp[i-1][S_1][S_2]$$(k$ $bitand$ $S_1=0)$，其中k是当前数的质因数集合，$bitand$是位与
滚动数组优化一下，把第一维去掉，总效率是$O(2^{20}n)$
100pt
这时有什么变化了呢？没错，n到了500以后可用的质因数变多了，我们无法把它们全部都压进一个数里面了
注意到，一个小于500的数，最多只可能有1个比22大的质因子
所以我们可以把这个质因子单独拿出来记录一下（没有就记为0）
然后，我们把2-n这些数按照大质因子大小排序，这样令大质因子相同的数排在一起（也就是不能甲乙同时选的）
我们记录三个相同数组：$dp[S_1][S_2],f1[][],f2[][]$，因为小质因数只有8个，所以$0\leq S_1,S_2\leq 255$
对于每一段大质因子相同的数，我们在这一段开始的时候把dp的值赋给f1和f2，然后在这一段内部用刷表法推f1和f2
具体来说这么做
$f1[i][S_1|k][S_2]+=f1[i-1][S_1][S_2]$$(k$ $bitand$ $S_2=0)$
或者$f2[i][S_1][S_2|k]+=f2[i-1][S_1][S_2]$$(k$ $bitand$ $S_1=0)$
其中k是当前数的小质因数集合（只有8个二进制位了）
大家应当看出来了，f1表示的就是这个大质因子让第一个人选，f2就是这个大质因子让第二个人选
这一段数推完以后，再把f1f2合并到dp里面，$dp[S_1][S_2]=f1[S_1][S_2]+f2[S_1][S_2]-dp[S_1][S_2]$
这里减掉一个dp是因为两种情况会重复统计两个人都不选的情况（也就是原来的dp[S_1][S_2]的值），减掉即可
最后答案就是$dp[0-255][0-255]$的和了
总时间复杂度为$O(n2^{16})$（居然比30pt做法还快【滑稽】）
Code:
详细的实现见代码
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
inline int read(){
int re=0,flag=1;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') flag=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re*flag;
}
int n,MOD;
int p[10]={0,2,3,5,7,11,13,17,19,0};
struct node{
int val,big,S;//big就是大质因数，S是小质因数集合
void init(){
int i,tmp=val;big=-1;
for(i=1;i<=8;i++){//分解质因数
if(tmp%p[i]) continue;
S|=(1<<i-1);
while(tmp%p[i]==0) tmp/=p[i];
}
if(tmp!=1) big=tmp;
}
}a[510];
inline bool cmp(node l,node r){
return l.big<r.big;
}
int pl(int l,int r){
l+=r;
return l>=MOD?l-MOD:l;
}
int dp[300][300],f1[300][300],f2[300][300];
int main(){
n=read();MOD=read();int i,j,k;
for(i=2;i<=n;i++) a[i-1].val=i,a[i-1].init();
sort(a+1,a+n,cmp);
dp[0][0]=1;
for(i=1;i<n;i++){
if(i==1||a[i].big!=a[i-1].big||a[i].big==-1){
memcpy(f1,dp,sizeof(f1));
memcpy(f2,dp,sizeof(f2));
}
for(j=255;j>=0;j--){
for(k=255;k>=0;k--){//因为是滚动数组，所以一定要倒着推
if(j&k) continue;
if((a[i].S&j)==0) f2[j][k|a[i].S]=pl(f2[j][k|a[i].S],f2[j][k]);
if((a[i].S&k)==0) f1[j|a[i].S][k]=pl(f1[j|a[i].S][k],f1[j][k]);
}
}
if(i==n-1||a[i].big!=a[i+1].big||a[i].big==-1){
for(j=0;j<=255;j++){
for(k=0;k<=255;k++){
if(j&k) continue;
dp[j][k]=pl(f1[j][k],pl(f2[j][k],MOD-dp[j][k]));
}
}
}
}
ll ans=0;
for(j=0;j<=255;j++){
for(k=0;k<=255;k++){
if((j&k)==0&&dp[j][k]) ans=pl(ans,dp[j][k]);
}
}
cout<<ans;
}