自动搬运

查看原文

来自洛谷，原作者为

	Ian_NIE 以梦为马，不负韶华 || 坐标北京人大附中

搬运于2025-08-24 22:59:04，当前版本为作者最后更新于2025-05-14 22:01:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

0x00 前言

读了半天没读懂白鸽子同学的题解，我自己也来写一篇。

0x01 题目大意

我们从一个初中生的角度理解题目。小奥大家都知道有个东西叫环形跑道，就是一些人在一个环形跑道上行动。这道题是一样的，一些行星在一个长度为 $1$（这个不是很重要，设一个就好）的跑道上进行运动，已经知道了每个行星运动完一圈所需要花的时间。

继续理解什么是所谓 Syzygy，朔望现象。就是两个行星，之间的距离是 $0$ 或 $\frac{1}{2}$，就是这个轨道的一侧或间距一半。我们会发现，存在很多种情况，比如只有两颗行星共线，或者三颗，甚至四颗。这时候题目告诉我们这些情况对答案的贡献是不一样的，需要乘上一个整数。在一个周期内（行星运行一圈所需时间的最小公倍数的倍数）把所有“朔望”的贡献加起来，初一这个周期的时刻数量，假设此时的结果是 $\frac{p}{q}$，答案 $ans$ 可以表示为：

$$\frac{p}{q} \equiv x \pmod {10^9 + 7}$$

0x01 题目分析 & 算法设计

不要被各种公式吓懵，这是一道紫题。

0x01 化简求答案的公式

首先我们需要解决这个答案 $ans$ 的求法。这个公式：

$$\frac{p}{q} \equiv x \pmod {10^9 + 7}$$

这时候我们利用费马小定理，当 $m$ 是质数且 $\gcd(x, m) = 1$ 时：

$$b^{-1} \equiv b^{m - 2} \pmod m$$

因为 $10^9 + 7$ 是质数并且显然 $\gcd(q, m) = 1$（因为 $q$ 是 $t_{1 \dots n}$ 的最小公倍数的倍数的因数，并且 $t_{1 \dots n}$ 均 $\le 10^9$，所以 $t_{1 \dots n}$ 的最小公倍数一定没有 $10^9 + 7$ 这个质因子，所以其因数更没有这个质因子，进而与 $10^9 + 7$ 互质），所以：

$$\frac{p}{q} = p \times q ^ {-1} \equiv p \times q^{10^9 + 7 - 2} = p \times q^{10^9 + 5} \equiv x \pmod {10^9 + 7} $$

即：

$$x \equiv p \times q^{10^9 + 5} \pmod {10^9 + 7}$$

现在我们的问题只在于解决 $\frac{p}{q}$ 了。

0x02 “朔望”怎么计算

我们先考虑简化问题，只考虑两个行星的系统。

设这两个行星的公转周期是 $t_1$ 和 $t_2$，不妨设 $t_1 < t_2$。所以运行速度是 $v_1 = \frac{1}{t_1}$ 和 $v_2 = \frac{1}{t_2}$，此时显然 $v_1 > v_2$。此时，“朔望”怎么理解，就是我在 “题目大意”部分已经说过的这句话：

继续理解什么是所谓 Syzygy，朔望现象。就是两个行星，之间的距离是 $0$ 或 $\frac{1}{2}$，就是这个轨道的一侧或间距一半。

所以，考虑一开始两个行星之间的距离是 $0$，下一次达到 $\frac{1}{2}$ 就是产生 $\frac{1}{2}$ 的路程差，再下一次达到 $0$ 就是再产生 $\frac{1}{2}$ 的路程差。根据 $t \times v = s$（行程问题的基础），即 $t = \frac{s}{v}$，所以对于两颗行星，“朔望”周期就是：

$$\frac{\frac{1}{2}}{v_1 - v_2} = \frac{1}{2(\frac{1}{t_1} + \frac{1}{t_2})} = \frac{t_1t_2}{2(t_2 - t_1)} $$

继续考虑“三星系统”。是行星，不是恒星，不是三体问题。 在证明三点共线是有一个证法，就是证明 $C$ 在直线 $AB$ 上。这时候我们可以先让行星 $1$ 和 $2$“朔望”，在计算什么时候 $1$ 与 $3$“朔望”，然后三星同时“朔望”在周期 $T$ 里面的“朔望”次数就是（不妨设 $t_1 < t_2 < t_3$）：

$$\gcd(\frac{T \,\cdot\, 2(t_2 - t_1)}{t_1t_2}, \frac{T \,\cdot\, 2(t_3 - t_1)}{t_1t_3}) $$

另外，对于周期 $T$，因为影响答案的是概率，所以 $T$ 只要是 $t_{1 \dots n}$ 的最小公倍数的倍数即可。显然当 $T = \prod t_i$ 时满足要求，所以这时候，我们粗略地把 $T$ 看作 $\prod t_i$。所以显然所有的 $\frac{T \,\cdot\, 2(t_j - t_i)}{t_it_j}$，满足 $t_i < t_j$，一定是正整数。

进而，以此类推，对于一个 $k$ 星系统，$k$ 星“朔望”在 $T$ 内的次数就是 $\gcd ^ k _{i = 2} \frac{T \,\cdot\, 2(t_i - t_1)}{t_1t_i}$，即计算所有 $2 \,\sim\, k$ 中所有与 $1$“朔望”的周期最小公倍数。

这样，数学部分也就解决了。

0x03 算法设计

观察我们得到的式子，首先先把 $2$ 提出来，然后预处理 $\frac{T}{t_1t_i}$ 和 $t_i - t_1$ 的每一个质因数，因为 $\gcd$ 本质就是质因数的运算。两者乘起来之后可以发现实质上不同的质因数数量很少，所以考虑直接暴力存储并且在以 $10^9 + 7$ 为模数的情况下求解答案。

我们直接选择一些行星，时间复杂度 $O(n^2)$，设总质因数个数为 $p$，此时进行数学计算的时间复杂度为 $O(n + w)$，整体时间复杂度 $O(2^n(n + w))$。

但是，在我们的算法里面根本没有考虑在当前这个行星中，该内部“朔望”没有更多的集合外的行星也发生了“朔望”。所以，我们需要再使用 IFWT 算法在 $O(w2^n)$ 的时间复杂度内实现该过程，按照前面的公式求取答案即可。

0x04 代码实现

这是一道大模拟，只需要注意一些细节即可。

IFWT 算法：

这里我的讲解比较粗略，直接放代码：

void IFWT(ll *f)
{
    for(int i = 1; i <= n; i++)
    {
        for(int st = tot; st >= 1; st--)
        {
            if(!((st >> (i - 1)) & 1)) continue;
            int nw = st ^ (1 << (i - 1));
            cnts[nw] = (cnts[nw] - cnts[st] + mo) % mo;
        }
    }
}

其他的讲解相对详细，可以直接写出代码，具体代码大家直接参考原题解就好了，只是我认为我的思路更加详细。

0x05 后记

本人水平不高，有问题请在评论区指出。本文对白鸽子同学的题解有大量的参考，但是我认为原题解的讲解不够详细，故又发文解释。

AC 记录。