首先注意到选择了一个数就是选择了它的所有素因子，而不超过$\sqrt{n}$的素数至多只有8个，可以考虑状压. 超过的那些我们先不管.
我一开始想的是枚举每个素数被分在哪边，这样是$3^8$的，但是我没想出来. 事实上完全可以暴力一点到$4^8$，这样可以把状态表示为$(s _1,s _2)$，即第一个人选了集合$s _1$，第二个人选了集合$s _2$（可以有交），最后把所有$s _1\cap s _2=\emptyset$的状态的答案加起来即可.
现在考虑大于$\sqrt{n}$的素因子，每个数最多只有一个，因此我们可以把数按照这个素因子来分类. 我一开始的想法是对每一类分别dp再合并起来，但是发现不方便合并. 很多这种不方便合并的情况，可以考虑在前一个的基础上去dp下一个.
具体来讲，让$f _{j,k}$表示之前dp出来的结果，dp出$g _{j,k}$和$h _{j,k}$分别表示只有第一/二个人能选当前这一类，最后两人选的集合为$j,k$的方案数，最后再让$f _{j,k}=g _{j,k}+h _{j,k}-f _{j,k}$，最后一项是因为两个人都不选这一类的情况被算了两次.
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
using namespace std;
const ele p[]={2,3,5,7,11,13,17,19};
ele n,P,f[maxs][maxs],g[maxs][maxs],h[maxs][maxs],t1[maxs][maxs],t2[maxs][maxs];
vector<ele> v[maxn];
inline ele getv(ele x,ele i){
return (x>>i)&1;
}
inline ele& setv(ele&x,ele i,ele k){
x=x&~(1<<i);
x=x|(k<<i);
return x;
}
inline ele& add(ele&a,ele b){
return a+b>=P?((a+=b)-=P):(a+=b);
}
int main(){
scanf("%d%d",&n,&P);
for (int i=2; i<=n; ++i){
ele tmp=i,s=0;
for (int j=0; j<K; ++j)
if (tmp%p[j]==0){
setv(s,j,1);
while (tmp%p[j]==0) tmp/=p[j];
}
v[tmp].push_back(s);
}
memset(f,0,sizeof(f)); f[0][0]=1;
for (int i=0; i<v[1].size(); ++i){
memcpy(t1,f,sizeof(f));
for (int j=0; j<maxs; ++j)
for (int k=0; k<maxs; ++k)
if (f[j][k]){
add(t1[j|v[1][i]][k],f[j][k]);
add(t1[j][k|v[1][i]],f[j][k]);
}
memcpy(f,t1,sizeof(f));
}
for (int i=2; i<=n; ++i)
if (v[i].size()){
memcpy(g,f,sizeof(g)); memcpy(h,f,sizeof(h));
for (int r=0; r<v[i].size(); ++r){
memcpy(t1,g,sizeof(g)); memcpy(t2,h,sizeof(h));
for (int j=0; j<maxs; ++j)
for (int k=0; k<maxs; ++k){
add(t1[j|v[i][r]][k],g[j][k]);
add(t2[j][k|v[i][r]],h[j][k]);
}
memcpy(g,t1,sizeof(g)); memcpy(h,t2,sizeof(h));
}
for (int j=0; j<maxs; ++j)
for (int k=0; k<maxs; ++k){
f[j][k]=P-f[j][k];
add(add(f[j][k],g[j][k]),h[j][k]);
}
}
ele ans=0;
for (int j=0; j<maxs; ++j)
for (int k=0; k<maxs; ++k)
if (!(j&k)) add(ans,f[j][k]);
printf("%d\n",ans);
return 0;
}