“$N$ 有不多于 $6$ 个不同的质因数”这条信息比较重要。

两个正整数 $a,b$ 若 $\gcd(a,b)=1$ 则 $a$ 与 $b$ 互质。若 $a,b$ 的质因数分解中不存在相同质因数则 $a$ 与 $b$ 互质。

因此，“不超过 $1$ 个数与 $x$ 不互质”可以转化为不超过一个数与 $x$ 有相同质因数。

考虑状态压缩维护这样的质因数状态（有或无）。记该二进制数 $S$ 的位数有 $len$ 位，则有 $2^{len}-1$ 个二进制状态。注意到 $x=2\times 3$ 和 $x=2^3\times 3$ 这两个数在状态中是等价的。所以考虑计算每一种数的个数 $cnt_S$。

::::success[怎么算？] 使用乘法原理，对 $N$ 进行质因数分解，得 $N=p_1^{c_1}\times p_2^{c_2}...\times p_{n}^{c_n}$，若二进制第 $i$ 位为 $1$，则这个质因数的指数可能是 $1\sim c_i$，则 $cnt_S\leftarrow cnt_S\times c_i$；若二进制第 $i$ 位为 $0$，则这个质因数的指数是 $0$。 ::::

接着，考虑如何计算题目中“不超过一个数与 $x$ 有相同质因数”。

可以用三进制状压表示每一种数还能选的数量，$0$ 表示还能选 $2$ 个，$1$ 表示还能选 $1$ 个，$2$ 表示不能选。则该三进制数的位数有 $2^{len}-1$ 位，则有 $3^{2^{len}-1}$ 个三进制状态。显然不是所有状态都会被枚举到。

用 dfs 转移，枚举将要选的数的种类，再枚举这种数会影响哪些数（即有相同质因数的数的种类）。

注意要用四进制维护，并使用 __int128。

::::info[为什么用四进制？] 如果用三进制，则取第 $i$ 位等操作需模拟，单次时间复杂度是 $O(2^{len}-1)$ 的，会超时。

使用四进制，可以类似二进制，使用位运算，单次时间复杂度是 $O(1)$ 的。 ::::