这题写挺久了。。。然后最近重构了一遍代码，始终过不了样例，求有闲心的同学帮忙看一下，谢谢。

大致思路写注释里了。

/*
暴力就f[i][s1][s2]，转移f[i+1][s1|k][s2]+=f[i][s1][s2],f[i+1][s1][s2|k]+=f[i][s1][s2]。
大质因子最多一个，单独拿出来做dp。onedp[i][s1][s2]表示第一个人选了这个大因子，anodp同理。
然后合并答案dp[i][s1][s2]=onedp+anodp-dp
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int up=1<<8;
int n,p,onedp[2][(1<<8)+5][(1<<8)+5],anodp[2][(1<<8)+5][(1<<8)+5],dp[2][(1<<8)+5][(1<<8)+5],turn,ans;
int pri[10]={2,3,5,7,11,13,17,19};
struct node
{
	int lar,nor;
}num[510];
bool cmp(node one,node ano)
{
	return one.lar<ano.lar;
}
int main()
{
	// freopen("test.out","w",stdout);
	scanf("%d%d",&n,&p);
	n--;
	for(int i=1;i<=n;++i)
	{
		int tmp=i+1;
		for(int j=0;j<8;++j)
		{
			if(tmp%pri[j]==0)
			{
				while(tmp%pri[j]==0)	tmp/=pri[j];
				num[i].nor|=(1<<j);
			}
		}
		num[i].lar=tmp;
	}
	sort(num+1,num+n+1,cmp);
	dp[0][0][0]=1;
	for(int i=1;i<=n;++i)
	{
		if(i==1||num[i].lar==1||(num[i].lar^num[i-1].lar))
		{
			for(int j=0;j^up;++j)
			{
				for(int k=0;k^up;++k)
				{
					onedp[turn][j][k]=dp[turn][j][k];
					anodp[turn][j][k]=dp[turn][j][k];
				}
			}
		}
		for(int j=0;j^up;++j)
		{
			for(int k=0;k^up;++k)
			{
				if(!(j&k))
				{
					if(!(num[i].nor&j))
					{
						anodp[turn^1][j][k|num[i].nor]=(anodp[turn^1][j][k|num[i].nor]+anodp[turn][j][k])%p;
						// printf("%d %d %d %d\n",j,k,anodp[turn^1][j][k|num[i].nor],anodp[turn][j][k]);
					}
					if(!(num[i].nor&k))	onedp[turn^1][j|num[i].nor][k]=(onedp[turn^1][j|num[i].nor][k]+onedp[turn][j][k])%p;
					// printf("%d %d\n",anodp[turn^1][j][k],onedp[turn^1][j][k]);
				}
			}
		}
		if(i==n||num[i].lar==1||(num[i].lar^num[i+1].lar))
		{
			for(int j=0;j^up;++j)
			{
				for(int k=0;k^up;++k)
				{
					if(!(j&k))	dp[turn^1][j][k]=(onedp[turn^1][j][k]+anodp[turn^1][j][k]-dp[turn][j][k]+p)%p;
				}
			}
		}
		turn^=1;
	}
	for(int i=0;i^up;++i)
	{
		for(int j=0;j^up;++j)
		{
			if(!(i&j))	ans=(ans+dp[turn][i][j])%p;
		}
	}
	printf("%d\n",ans);
	return 0;
}

如果是哪里手残了请不吝赐教。