设一个数 $n$ 除尽其 $2,3$ 因子后的数为 $f(n)$。

显然有 $f(n)\le n$。

然后只有 $f(n)$ 相同的数才有可能互相影响。

因此可以用 $f(n)$ 来划分等价类。

即，对二元关系 $\sim$，我们定义

$$A\sim B\Leftrightarrow f(A)=f(B)$$

显然这是一个等价关系，只有在同一个等价类内的数才可能能相互影响取法。

设等价类 $\bar a$ 中最小的元素为其代表元，也即 $f(a)$。

考虑等价类中每个元素 $a=f(a)2^x3^y$，$(x,y)$ 构成其在等价类内的坐标，$x$ 是列标号，$y$ 是行标号。

譬如，在 $n=30$ 时的等价类 $\bar 5$ 中，我们有

• $5:(0,0)$
• $10:(1,0)$
• $15:(0,1)$
• $20:(2,0)$
• $30:(1,1)$

即

$$\begin{matrix} \circ&\circ&\circ\\ \circ&\circ\\ \end{matrix} $$

显然题意就被转化为了任意两个在同一个等价类内坐标相邻的点不可同时选择。

由于各个等价类不相干扰，答案用乘法原理即可合并，故直接求出单个等价类的答案即可。

由于一个等价类 $\bar a$ 的 $(x,y)$ 的范围可以不难由 $\lfloor\frac n{f(a)}\rfloor$ 唯一确定，我们接下来直接对坐标讨论。对 $\bar a$ 的方案数我们记为 $g(\lfloor\frac n{f(a)}\rfloor)$。

首先，从刚刚那个样例可以看出，坐标一定排列成 Young 表（Ferrers 图）状，我们就是从中选择若干互不相邻的点。

于是我们可以状压 dp，从上一列的信息转移到这一列来。

设有 $a$ 行，$b$ 列，每一列的状态有不多于 $2^a$ 种，通过补子集枚举逐列转移状态（记得要保持互不相邻）要 $O(3^a)$ 每次（或用 FMT 做到 $O(a2^a)$），进行 $b$ 轮即 $O(b3^a)$（或 $O(ab2^a)$）。

对于 $g(n)$ 的单次计算，其复杂度上界为 $O(n\log n)$ 或 $O(n^{\log_32}\log^2n)$，且严重跑不满。（后者约 $O(n^{0.63}\log^2n)$，实际预计无明显优势）

好，我们现在答案即

$$\sum_k[2\nmid k][3\nmid k]g(\lfloor\frac nk\rfloor) $$

对这个东西，我们可以通过记忆化或数论分块等手法使之只用访问互不相同的 $O(\sqrt n)$ 类 $g$，且大小有显著差异。

当 $g(n)$ 用 $O(n\log n)$ 的时间计算时，答案的计算时间可以简单的估计为 $O(n\log^2n)$ 的。

当 $g(n)$ 用 $O(n^{\log_32}\log^2n)$ 的时间计算时，答案的计算时间可以用积分估计为 $O(n^{\log_3\sqrt6}\log^2n)$ 的，可近似认为是 $O(n^{0.82}\log^2n)$ 的。

但以上分析均仅给出上界，未给出确界。其实际效率应当明显比分析更高。