给定 ~ 这 个数，让两个人分别选出一些数，使得对于第一个人选择的任意一个数 和第二个人选择的任意一个数 ，有 ，求方案数。
链接
题解
因为题目要求的条件不互质就是指没有相同的质因子，一个显然的思路是求出这些数的所有质因子，用 （、 为二进制集合）表示第一个人选择的质因子集合为 、第二个人为 的方案数。
但是这些数的质因子太多，无法进行状压，如果我们不考虑每个数 的（最多一个的）大于 的质因子，则质因子只有 个 —— ，将这些质因子状压。
考虑另一个质因子的影响，设它为 ，则如果一个人选了一个含有质因子 的数，另一个人不能选取任何含有质因子 的数。
将所有数按照 分组，对于每一组，以二进制集合的方式储存其所有数的其它质因子，设第 个数为 。一组数中，最多由某一个人选若干个。
设 表示不选当前组的情况下，第一个人所选集合为 ，第二个人所选集合为 的方案总数。
对于每一个集合，设 表示组内前 个数，全部由第 个人来选，第一个人所选集合为 ，第二个人所选集合为 的方案总数。
转移时，枚举组内每个数 ，分别以 和 更新 和 。
注意到枚举 和 时，所枚举到的 或 均为 或 的字集，体现在十进制意义下，即 、。这启发我们可以像背包一样，滚动掉第一维 ，从大到小枚举 和 ，同时刷表更新 和 。
最后一个问题，对于每个没有大于 的因子的数 ，将这些数每个单独分一组即可。
代码
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <vector>
const int MAXN = 500;
const int MAXK = 8;
const int MAXSTAT = 1 << 8;
const int PRIMES[] = { 2, 3, 5, 7, 11, 13, 17, 19 };
int main() {
int n, p;
scanf("%d %d", &n, &p);
std::vector< std::vector<int> > v;
std::vector< std::pair<int, int> > tmp;
for (int i = 2; i <= n; i++) {
int x = i, t = 0;
for (int j = 0; j < 8; j++) {
if (x % PRIMES[j] == 0) {
while (x % PRIMES[j] == 0) x /= PRIMES[j];
t |= 1 << j;
}
}
tmp.push_back(std::make_pair(x, t));
}
std::sort(tmp.begin(), tmp.end());
for (std::vector< std::pair<int, int> >::const_iterator it = tmp.begin(); it != tmp.end(); it++) {
if (it == tmp.begin() || it->first == 1 || it->first != (it - 1)->first) {
v.resize(v.size() + 1);
}
v.back().push_back(it->second);
}
static int f[MAXSTAT][MAXSTAT], g[2][MAXSTAT][MAXSTAT];
f[0][0] = 1;
for (std::vector< std::vector<int> >::const_iterator it = v.begin(); it != v.end(); it++) {
memcpy(g[0], f, sizeof(f));
memcpy(g[1], f, sizeof(f));
// puts("new");
for (std::vector<int>::const_iterator it2 = it->begin(); it2 != it->end(); it2++) {
// printf("%d\n", *it2);
for (int a = MAXSTAT - 1; a >= 0; a--) {
for (int b = MAXSTAT - 1; b >= 0; b--) {
// printf("%d %d\n", a, b);
if (!(b & *it2)) /* printf("[0] += %d\n", g[0][a][b]), */ (g[0][a | (*it2)][b] += g[0][a][b]) %= p;
if (!(a & *it2)) /* printf("[1] += %d\n", g[1][a][b]), */ (g[1][a][b | (*it2)] += g[1][a][b]) %= p;
// printf("%d\n", *it2);
// printf("%d %d\n", g[0][a][b], g[1][a][b]);
}
}
}
for (int a = MAXSTAT - 1; a >= 0; a--) {
for (int b = MAXSTAT - 1; b >= 0; b--) {
f[a][b] = ((g[0][a][b] + g[1][a][b] - f[a][b]) % p + p) % p;
}
}
}
int ans = 0;
for (int a = MAXSTAT - 1; a >= 0; a--) {
for (int b = MAXSTAT - 1; b >= 0; b--) {
if (!(a & b)) (ans += f[a][b]) %= p;
}
}
printf("%d\n", ans);
return 0;
}