题目描述

为了庆祝 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$取模）。注意一个人可以不吃任何寿司。

输入格式

输入文件的第1行包含2个正整数$n,p$，中间用单个空格隔开，表示共有$n-1$种寿司，最终和谐的方案数要对$p$取模。

输出格式

输出一行包含1个整数，表示所求的方案模$p$的结果。

题目解析

转化一下题意，就是求小G和小W分别选择一个整数集合，使得不同集合间任意两数均互质的方案数。

考虑整数的质因数分解，两个整数互质当且仅当两者没有相同的质因子。如果我们将整数集合$S$内所有整数所含的质因子表示为一个新集合$S'$，集合$T$内所有整数所含的质因子表示为一个新集合$T'$。可以知道若集合$S,T$满足题意，当且仅当$S',T'$没有交集。

我们发现，对于任何小于$n$的正整数，至多有一个$\ge \sqrt{n}$的质因子。如果有一个人选择了包含质因子$p$的整数，那么另一个人不能选取任何包含质因子$p$的整数。这启发我们将所有存在大质因子整数以它们的大质因子分类。同一类的整数只能被一个人选择。

因为$\le n$的质因子只有$8$个，所以在没有大质因子的情况下，我们可以把一个人选择的质因子集合表示为一个$2 ^ 8$的二进制数$S$。设选择到第$i$个整数时小$G$选择的集合为$S$，小$W$选择的集合为$T$的方案数为$f(i,S,T)$。则有

$$f(i,S|P(i),T) += f(i - 1,S,T) \\ f(i,S,T|P(i)) += f(i-1,S,T)$$

其中$P(i)$是整数$i$的质因子集合。上述方程显然是可以用滚动背包优化一维空间的。

考虑有大质因子的情况。假设我们现在考虑到质因子$p$，另设$g(0,i,S,T)$为大质因子分给小$G$，考虑到第$i$个整数时小$G$此时质因子集合为$S$，小$W$质因子集合为$T$的方案数，同理$g(1,i,S,T)$为大质因子分给小$W$的方案数。则有

$$g(0,i,S|P(i),T) += g(0,i-1,S,T) \\ g(1,i,S,T|P(i)) += g(1,i-1,S,T)$$

$P(i)$意义如上所述。同理，这个方程也可以优化掉一位空间。在开始一类数的DP时，我们先令

$$g(0,S,T) = f(S,T) \\ g(1,S,T) = f(S,T)$$

在DP完成后，再令

$$f(S,T) = g(0,S,T) + g(1,S,T) - f(S,T)$$

因为两个人均不选这类数的情况在$g(0,S,T)$和$g(1,S,T)$中均出现了。

总时间复杂度$O(n 2 ^ {16})$。