P2150

非常好的经典题！

先有一个暴力的想法：一个一个枚举每个数加进哪个集合或不加，对于两个集合，分别状压记录每个质因数是否被选中，转移。状态数是 $O(2^{\dfrac{2n}{\ln n}})$ 的（$\sum_{i\le n}[i\in P]\approx \dfrac{n}{\ln n}$）。显然过不了。

又有另一个想法：为什么不能将有同样质因数的数拿出来，钦定他们其中被选中的都在同一个集合呢？但是发现可能出现一种情况，就是这些数中存在一个更小的质因数 $p$，而 $p$ 这个质因数在另一个集合也出现了。

然后你就发现我们其实可以综合一下这两个做法！具体地，将每个数加进它最大的质因数所代表的集合。规定一个集合的数不同时出现在两个答案集合中。然后，为了避免上面所提到的问题，我们可以记录部分质因数。哪部分呢？实际上只用 $\le\sqrt n$ 的就行了，因为如果一个数有不止一个质因数，则其中至少有一个 $\le\sqrt n$，至多有一个 $>\sqrt n$。于是这么做就是正确的。

时间复杂度 $\Omega(2^{16}n)$。

code：

int n,m,mod,dp[N][N][3],f[N][N][3],pm[M],fac[M],c[M];
bool vis[M];
vector<int> a[M];
map<int,int> mp;
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
void Yorushika(){
	scanf("%d%d",&n,&mod);
	mp[2]=0,mp[3]=1,mp[5]=2,mp[7]=3,mp[11]=4,mp[13]=5,mp[17]=6,mp[19]=7;
	rep(i,2,n){
		if(!vis[i]){
			pm[++m]=i,fac[i]=i;
		}
		rep(j,1,m){
			if(pm[j]>n/i){
				break;
			}
			vis[i*pm[j]]=1,fac[i*pm[j]]=pm[j];
			if(i%pm[j]==0){
				break;
			}
		}
		int tmp=i,mx=0;
		while(tmp>1){
			if(mp.count(fac[tmp])){
				c[i]|=1<<mp[fac[tmp]];
			}
			mx=max(mx,fac[tmp]),tmp/=fac[tmp];
		}
		a[mx].eb(i);
	}
	const int mx=1<<8;
	dp[0][0][0]=1;
	rep(k,1,n){
		for(int i:a[k]){
			mems(f,0);
			rep(S,0,mx-1){
				rep(T,0,mx-1){
					if(!(T&c[i])){
						f[S|c[i]][T][1]=Mod(f[S|c[i]][T][1],Mod(dp[S][T][1],dp[S][T][0]));
					}
					if(!(S&c[i])){
						f[S][T|c[i]][2]=Mod(f[S][T|c[i]][2],Mod(dp[S][T][2],dp[S][T][0]));
					}
					rep(j,0,2){
						f[S][T][j]=Mod(f[S][T][j],dp[S][T][j]);
					}
				}
			}
			rep(S,0,mx-1){
				rep(T,0,mx-1){
					rep(j,0,2){
						dp[S][T][j]=f[S][T][j];
					}
				}
			}
		}
		rep(S,0,mx-1){
			rep(T,0,mx-1){
				dp[S][T][0]=Mod(dp[S][T][0],Mod(dp[S][T][1],dp[S][T][2]));
				dp[S][T][1]=dp[S][T][2]=0;
			}
		}
	}
	int ans=0;
	rep(S,0,mx-1){
		rep(T,0,mx-1){
			ans=Mod(ans,dp[S][T][0]);
		}
	}
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}