一个数内可能多个的质因数只有小于根号n的，500内这样的数只有8个，所以考虑状压

把2~n的数处理出小于根号500的质因数集压成s，以及大质数p（没有就是1），然后按p排序

根据题目要求，拥有一个质因数的只能给一个人，所以排序后能给一个人的大质数就是一个区间

然后设f[s1][s2]为一人选s1，另一人选s2的方案数，注意这里的s只压了小于根号500的八个质数

设g[0/1][s1][s2]为一人选s1，另一人选s2的，当前枚举的大质数给小G/小W的方案数

正常转移即可

然后注意把g转到f上时应该是f[j][k]=g[0][j][k]+g[1][j][k]-f[j][k]，也就是减掉被算了两次的，当前枚举大质数都不选的情况

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=505,p[]={2,3,5,7,11,13,17,19};

int n;

long long mod,f[N][N],g[2][N][N],ans;

bool v[N];

struct qwe

{

	int s,p;

}a[N];

bool cmp(const qwe &a,const qwe &b)

{

	return a.p<b.p;

}

int main()

{

	scanf("%lld%lld",&n,&mod);

	for(int i=2;i<=n;i++)

	{

		int x=i;

		for(int j=0;j<8;j++)

			if(x%p[j]==0)

			{

				a[i].s|=(1<<j);

				while(x%p[j]==0)

					x/=p[j];

			}

		a[i].p=x;

	}

	sort(a+2,a+1+n,cmp);

	f[0][0]=1;

	for(int i=2;i<=n;i++)

	{

		if(i==2||a[i].p!=a[i-1].p||a[i].p==1)

		{

			memcpy(g[0],f,sizeof(f));

			memcpy(g[1],f,sizeof(f));

		}

		for(int j=255;j>=0;j--)

			for(int k=255;k>=0;k--)

				if(!(j&k))

				{

					if(!(a[i].s&k))

						g[0][a[i].s|j][k]=(g[0][a[i].s|j][k]+g[0][j][k])%mod;

					if(!(a[i].s&j))

						g[1][j][a[i].s|k]=(g[1][j][a[i].s|k]+g[1][j][k])%mod;

				}

		if(i==n||a[i].p==1||a[i].p!=a[i+1].p)

			for(int j=255;j>=0;j--)

				for(int k=255;k>=0;k--)

					if(!(j&k))

						f[j][k]=(g[0][j][k]+g[1][j][k]-f[j][k])%mod;

	}

	for(int i=255;i>=0;i--)

		for(int j=255;j>=0;j--)

			if(!(i&j))

				ans=(ans+f[i][j])%mod;

	printf("%lld\n",(ans+mod)%mod);

	return 0;

}