Description
为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。
在晚宴上,主办方为大家提供了 n?1 种不同的寿司，编号 1,2,3,…,n?1，其中第 i 种寿司的美味度为 i+1 （即寿司的美味度为从 2 到 n）。
现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 x 的寿司，小 W 品尝的寿司中存在一种美味度为 y 的寿司，而 x 与 y 不互质。
现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 p 取模）。注意一个人可以不吃任何寿司。
Input
输入文件的第 1 行包含 2 个正整数 n,p，中间用单个空格隔开，表示共有 n 种寿司，最终和谐的方案数要对 p 取模。
Output
输出一行包含 1 个整数，表示所求的方案模 p 的结果。
Sample Input
3 10000
Sample Output
9
HINT
2≤n≤500
0<p≤1000000000
Source
这题也是很服气的。
题目大意：有[2,n]个数,现在把它们分成两组，使得任意两组中各一个数互质。
如果n较小，可以考虑暴力dp。
将质因数分成两组，交集为空。
将是否选选了某个质因数进行状态压缩。
设f[i][j]表示甲的质因子是i，乙的是j，则可以转化为01背包。
如果n较大，可以看出对于每一个数n，大于根号n的质因数最多一个（废话）。
哈哈哈（缓解一下尴尬）。
如果将具有相同大质因数的数字归为一组，对于这一组，转移与小质数相似。
设g[0][j][k],g[1][j][k]分别表示大质数在甲和乙。
则合并时f[j][k]=g[0][j][k]+g[1][j][k]-f[j][k]因为不选的情况在两者中都出现了，所以减去一次。
最后数组一定不要开得太大，会浪费时间。
另：匍匐在蹂躏此题的大爷脚下，不由自主的呐喊：“。。。”
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=505;
int n,pri[11]={2,3,5,7,11,13,17,19};
long long p,ans,f[305][305],g[2][305][305];
struct node
{int x,y;
}a[N];
bool cmp(node c,node d)
{if(c.y==d.y)return c.x<d.x;return c.y<d.y;
}
int main()
{scanf("%d%lld",&n,&p);for(int i=2;i<=n;i++){int t=i;for(int j=0;j<=7;j++)if(t%pri[j]==0){a[i].x|=(1<<j);while(t%pri[j]==0)t/=pri[j];}a[i].y=t;}sort(a+2,a+n+1,cmp);f[0][0]=1;int end=(1<<8)-1;for(int i=2;i<=n;i++){if(i==2||a[i].y==1||a[i].y!=a[i-1].y){memcpy(g[0],f,sizeof(f));memcpy(g[1],f,sizeof(f));}for(int j=end;j>=0;j--)for(int k=end;k>=0;k--)if((j&k)==0){if((a[i].x&k)==0)g[0][j|a[i].x][k]=(g[0][j|a[i].x][k]+g[0][j][k])%p;if((a[i].x&j)==0)g[1][j][k|a[i].x]=(g[1][j][k|a[i].x]+g[1][j][k])%p;}if(i==n||a[i].y==1||a[i+1].y!=a[i].y)for(int j=end;j>=0;j--)for(int k=end;k>=0;k--)if((j&k)==0)f[j][k]=(g[0][j][k]+g[1][j][k]-f[j][k])%p;}for(int j=0;j<=end;j++)for(int k=0;k<=end;k++)if((j&k)==0)ans+=f[j][k],ans%=p;ans+=p,ans%=p;printf("%lld\n",ans);return 0;
}