这个题一开始想到了唯一分解定理，然后状压。但是显然数组开不下，后来想到每个数（n<500）大于19的素因子只可能有一个，所以直接单独存就行了。
然后正常状压dp就很好搞了。
题干：
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
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; const int mod = 998244353; typedef double db; typedef long long ll; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') {x = x * 10 + c - '0';} if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } ll pri[12] = {0,2,3,5,7,11,13,17,19,0}; struct node { ll val,big,s; void init() { ll tmp = val; big = -1; duke(i,1,8)//only { if(tmp % pri[i]) continue; s |= (1 << (i - 1)); while(tmp % pri[i] == 0) tmp /= pri[i]; } if(tmp != 1) big = tmp; } }a[1010]; bool cmp(node a,node b) { return a.big < b.big; } ll n; ll p; ll pl(ll l,ll r) { l += r; return l >= p ? l - p : l; } ll f1[300][300],f2[300][300]; ll dp[300][300]; int main() { read(n);read(p); duke(i,2,n) a[i - 1].val = i,a[i - 1].init(); sort(a + 1,a + n,cmp); dp[0][0] = 1; duke(i,1,n - 1) { if(i == 1 || a[i].big != a[i - 1].big || a[i].big == -1) { memcpy(f1,dp,sizeof(f1)); memcpy(f2,dp,sizeof(f2)); } lv(j,255,0) { lv(k,255,0) { if(j & k) continue; if((a[i].s & j) == 0) f2[j][k | a[i].s] = pl(f2[j][k | a[i].s],f2[j][k]); if((a[i].s & k) == 0) f1[j | a[i].s][k] = pl(f1[j | a[i].s][k],f1[j][k]); } } if(i == n - 1 || a[i].big != a[i + 1].big || a[i].big == -1) { duke(j,0,255) { duke(k,0,255) { if(j & k) continue; dp[j][k] = pl(f1[j][k],pl(f2[j][k],p - dp[j][k])); } } } } ll ans = 0; duke(j,0,255) { duke(k,0,255) { if((j & k) == 0 && dp[j][k]) ans = pl(ans,dp[j][k]); // cout<<dp[j][k]<<" "; } // cout<<endl; } printf("%lld ",ans); return 0; }