神题神题，今天来玩几道状压题。
首先考虑若 \(n \le 20\) 怎么做：
显然记录一下质因子集合即可。
然而 \(n \le 500\)，但是根据一些基本的数论知识，每个数最多只有一个超过 \(19\) 的质因子（下称大质因子）。
于是可以考虑每个数的大质因子预处理出来，然后把大质因子相同的放在一起处理。
具体地说，就是对于每个连续段，考虑把这个大质因子给小 G 或小 W，然后合并答案（注意不选大质因子的会被算两次，容斥掉）。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using namespace std;
const int N = 500;
const int P = 8;
const int prime[] = {0,2,3,5,7,11,13,17,19};
const int full = (1 << P) - 1;
int n;
long long mod,f[(1 << P) + 5][(1 << P) + 5],g[2][(1 << P) + 5][(1 << P) + 5],ans;
struct note
{
int s,w;
inline bool operator<(const note &o) const
{
return w < o.w;
}
} a[N + 5];
int main()
{
scanf("%d%lld",&n,&mod),f[0][0] = 1;
for(register int i = 2,v;i <= n;++i)
{
v = i;
for(register int j = 1;j <= P && v > 1;++j)
{
!(v % prime[j]) && (a[i - 1].s |= (1 << j - 1));
for(;!(v % prime[j]);v /= prime[j]);
}
a[i - 1].w = v;
}
sort(a + 1,a + n);
for(register int i = 1;i < n;++i)
{
if(a[i].w == 1 || (a[i].w ^ a[i - 1].w))
memcpy(g[0],f,sizeof g[0]),memcpy(g[1],f,sizeof g[1]);
for(register int j = full;~j;--j)
for(register int k = full;~k;--k)
if(!(j & k))
!(a[i].s & k) && (g[0][j | a[i].s][k] = (g[0][j | a[i].s][k] + g[0][j][k]) % mod),
!(a[i].s & j) && (g[1][j][k | a[i].s] = (g[1][j][k | a[i].s] + g[1][j][k]) % mod);
if(a[i].w == 1 || (a[i].w ^ a[i + 1].w))
for(register int j = full;~j;--j)
for(register int k = full;~k;--k)
f[j][k] = (g[0][j][k] + g[1][j][k] - f[j][k] + mod) % mod;
}
for(register int i = 0;i <= full;++i)
for(register int j = 0;j <= full;++j)
!(i & j) && (ans = (ans + f[i][j]) % mod);
printf("%lld\n",ans);
}