将2~n的整数划分到两个集合，使得两个集合中任意两个元素互质，求方案数。
对于n<=30的情况是很容易想到的，将每个数\(i\)求出它的质因子集合\(K_{i}\)。
很容易可以发现，30以内的质数仅有10种。故而我们就有了一个\(O(2^{202}n)\)的做法。
对于n<=500的情况，似乎用上述的做法并不是十分可行，无论是时间复杂度还是空间复杂度都是不可接受的。
但是我们发现，有且仅有7个质数，在500以内会作为因数出现多次。我们是不是可以用一种奇技淫巧把大于19的质数处理掉呢？
我们惊讶地发现，由于所有较大的质数会且只会出现一次，那么很显然所有最大质因子是较大质数且最大质因子相同的数只能放到一个集合里。
故而我们把所有数按照最大质因子排序，然后从小到大遍历。当最大质因子成为较大质数的时候，不再使用原来的数组，而是将「这个质因子一个都没选」的情况复制到两个新的数组f2[2][1<<7][1<<7]。
每一次更换最大质因子的时候都从原数组继承DP值，然后在这里面对每一个是放在A还是放在B的情况来更新：
$$f_{S_1,S_2} = f2_{0,S_1,S_2} + f2_{1,S_1,S_2} – f_{S_1,S_2}$$
之所以最后还要减去原来的值是因为，两个新数组的最终结果各自都是从原来的「这个质因子一个都没选」的情况复制过来的，因此「这个质因子一个都没选」的情况就会被统计两次。
#include<iostream>
#include<cstdio>
#include<algorithm>
/*
*/
const int P[8]={2,3,5,7,11,13,17,19};
const int MAX=1<<8;
long long MOD;
long long f[MAX][MAX],f2[2][MAX][MAX];
struct data{
int v;
int big;
int K;
inline void init(int X){
v=X,big=0;
int nw=v;K=0;
for(int i=0;i<8;++i){
if(!(nw%P[i])){
K|=(1<<i);
}
while(!(nw%P[i])){
nw/=P[i];
}
}
if(nw>1){
big=nw;
}
}
inline bool operator<(const data &B)const{
return big<B.big;
}
}a[505];
int n;
void init(){
scanf("%d%lld",&n,&MOD);
--n;
for(int i=1;i<=n;++i){
a[i].init(i+1);
}
std::sort(a+1,a+1+n);
int lst=0x3f3f3f3f;
f[0][0]=1;
for(int i=1;i<=n;++i){
if(a[i].big){
lst=i;
break;
}
for(int j=MAX-1;~j;--j){
// 注意这里要-1
for(int k=MAX-1;~k;--k){
f[j][k|a[i].K]+=f[j][k];f[j|a[i].K][k]+=f[j][k];
f[j][k|a[i].K]%=MOD;f[j|a[i].K][k]%=MOD;
}
}
}
for(int i=lst;i<=n;++i){
if(a[i].big!=a[i-1].big){
for(int j=0;j<MAX;++j){
for(int k=0;k<MAX;++k){
f2[0][j][k]=f2[1][j][k]=f[j][k];
}
}
}
for(int j=MAX-1;~j;--j){
for(int k=MAX-1;~k;--k){
if(j&k){
continue;
}
if(!(k&a[i].K)){
f2[0][j|a[i].K][k]+=f2[0][j][k];
f2[0][j|a[i].K][k]%=MOD;
}
if(!(j&a[i].K)){
f2[1][j][k|a[i].K]+=f2[1][j][k];
f2[1][j][k|a[i].K]%=MOD;
}
}
}
if(a[i].big!=a[i+1].big){
for(int j=0;j<MAX;++j){
for(int k=0;k<MAX;++k){
f[j][k]=(f2[0][j][k]+f2[1][j][k]+(MOD-f[j][k]))%MOD;
}
}
}
}
long long ans=0;
for(int i=MAX-1;~i;--i){
for(int j=MAX-1;~j;--j){
if(i&j){
continue;
}
ans+=f[i][j];
ans%=MOD;
}
}
printf("%lld\n",ans);
}
int main(){
init();
return 0;
}