题目大意：
(A)和(B)是({2,3,ldots,n}(nle500))的不相交的子集，且(A)中的任一元素都与(B)中任一元素互质。求有序对((A,B))的种数。
思路：
OEIS中的说明：A260185。
考虑一个比较暴力的算法，首先求出每个数的质因数，(f[i][s1][s2])表示前(i)个数，(A)中有的质因数是(s1)，(B)中有的质因数是(s2)。转移方程显然。
对于一个数(x)，大于(sqrt x)的质因数最多只有一个，而(le sqrt{500})的质因数只有(8)个，对这(8)个质因数进行状压。
考虑大于根号的质因数，我们可以将大于根号的质因数相等的那些数拿出来，对于这些数放在(A/B)的情况用(f1)和(f2)两个数组分开DP。最后将答案合并到(f)中。
源代码：
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=501,P=8,M=1<<P;
const int p[]={2,3,5,7,11,13,17,19};
int mask[N],x[N],a[N],f[M][M],f1[M][M],f2[M][M];
inline bool cmp(const int &i,const int &j) {
return x[i]<x[j];
}
int main() {
const int n=getint(),mod=getint();
for(register int i=2;i<=n;i++) {
a[i]=x[i]=i;
for(register int j=0;j<P;j++) {
if(x[i]%p[j]!=0) continue;
mask[i]|=1<<j;
while(x[i]%p[j]==0) x[i]/=p[j];
}
}
std::sort(&a[2],&a[n]+1,cmp);
int i;
f[0][0]=1;
for(i=2;i<=n&&x[a[i]]==1;i++) {
const int v=a[i];
for(register int j=M-1;~j;j--) {
for(register int k=M-1;~k;k--) {
const int tmp=f[j][k];
if(!(mask[v]&j)) (f[j][k|mask[v]]+=tmp)%=mod;
if(!(mask[v]&k)) (f[j|mask[v]][k]+=tmp)%=mod;
}
}
}
for(;i<=n;i++) {
if(x[a[i]]!=x[a[i-1]]) {
memcpy(f1,f,sizeof f);
memcpy(f2,f,sizeof f);
}
const int v=a[i];
for(register int j=M-1;~j;j--) {
for(register int k=M-1;~k;k--) {
const int tmp1=f1[j][k],tmp2=f2[j][k];
if(!(mask[v]&j)) (f2[j][k|mask[v]]+=tmp2)%=mod;
if(!(mask[v]&k)) (f1[j|mask[v]][k]+=tmp1)%=mod;
}
}
if(x[a[i+1]]!=x[a[i]]) {
for(register int j=0;j<M;j++) {
for(register int k=0;k<M;k++) {
f[j][k]=((int64)f1[j][k]+f2[j][k]-f[j][k]+mod)%mod;
}
}
}
}
int ans=0;
for(register int j=0;j<M;j++) {
for(register int k=0;k<M;k++) {
(ans+=f[j][k])%=mod;
}
}
printf("%d
",ans);
return 0;
}