万能欧几里得

有一类问题可以归结为以下模型：

有一种元素，它们之间可以定义乘法，且乘法满足结合律。给定两个元素 \(X, Y\) 和正整数 \(n\) ，求

\[F(P, R, Q, n, X, Y) = \prod_{i=0}^n Y^{f(i) - f(i - 1)} X\]

其中 \(f(x) = \lfloor \frac{xP+R}{Q} \rfloor\) ，特别的 \(f(-1)=0\) ，也就是说第 \(i\) （从 \(0\) 开始）个 \(X\) 前面都有恰好 \(f(i)\) 个 Y 。

不难发现所有类欧几里得都可以归结为该模型。

解法

直奔主题，讲怎么做，其中奥妙自行体会。

以下把连乘展开构成的字符串称作 \(S\) 。

首先 \(n = 0\) 的时候可以直接求解，接下来假定 \(n \ge 1\) 。

如果 \(R \ge Q\) ，也就是 \(f(0) \ge 1\) ，那么可以把 \(S\) 开头的 \(Y\) 全部提出来，有

\[F(P, R, Q, n, X, Y) = Y^{\lfloor \frac{R}{Q} \rfloor} F(P, R \bmod Q, Q, n, X, Y)\]

接下来假定 \(R < Q\) ，那么 \(S\) 的开头一定是个 \(X\) 。

---

然后就可以来一波辗转相除，\(P \ge Q\) 时把 \(P\) 转换为 \(P \bmod Q\) ，否则交换 \(P, Q\) ，具体方法如下。

如果 \(P \ge Q\) ，不难发现把 \(S\) 中每相邻两个 \(X\) 之间都有至少一个 \(Y\) ，把这个 \(Y\) 绑在后面的 \(X\) 上，不断绑定，但是注意到第一个 \(X\) 是没法绑定的，把这个 \(X\) 提出来，有

\[F(P, R, Q, n, X, Y) = X F(P \bmod Q, R + P \bmod Q, Q, n - 1, Y^{\lfloor \frac{P}{Q} \rfloor} X, Y)\]

---

否则考虑交换 \(P, Q\) 的地位，如果放在二维平面上，就是翻转坐标系，由于懒得扯上数形结合，这里来点数学推导。

将 \(S\) 中的 \(X, Y\) 都从 \(0\) 开始编号，根据 \(F\) 的定义编号为 \(i\) 的 \(X\) 左边的 \(Y\) 的数量恰为 \(f(i)\) ，\(f\) 是个线性函数向下取整的形式。那么考虑第编号为 \(i\) 的 \(Y\) 左边的 \(X\) 的数量，设其为 \(g(i)\) ，不难发现 \(g\) 同样是个线性函数向下取整的形式！这意味着可以简单地交换 \(X, Y\) 的地位，从而交换 \(P, Q\) 。需要注意的是 \(S\) 的末尾有若干 \(X\) 需要特殊考虑。

那么现在的问题就是求 \(g(i)\) ，根据定义有

\[ \begin{aligned} g(i) &= \sum_{j \ge 0} [f(j) \le i] \\\\ &= \sum_{j \ge 0} [\lfloor \frac{Pj+R}{Q} \rfloor \le i] \\\\ &= \sum_{j \ge 0} [Pj + R - Q + 1 \le Qi] \\\\ &= \sum_{j \ge 0} [j \le \lfloor \frac{Qi-R+Q-1}{P} \rfloor] \\\\ &= \lfloor \frac{Qi+P-R+Q-1}{P} \rfloor \end{aligned} \]

于是，稍加整理，不难得到

\[F(P, R, Q, n, X, Y) = F(Q, P - R + Q - 1, P, t - 1, Y, X) X^{n - \lfloor \frac{Qt-R-1}{P} \rfloor}\]

其中 \(t\) 是 \(S\) 内 \(Y\) 的数量，有 \(t = \lfloor \frac{nP+R}{Q} \rfloor\) ，注意 \(t=0\) 的边界情况。

实例

咕咕咕。