「万能」Euclidean 算法

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

其中 \(f(i) = \lfloor \dfrac{Pi+R}{Q}\rfloor, f(-1) = 0\)​。\(X, Y\) 为操作序列，有乘法结合律，类比矩阵 \(\in\) 半群 \((S, \times)\)。

若 \(R \geq Q\)​，则 \(f(i)= \lfloor \dfrac{Pi+(R \bmod Q)}{Q}\rfloor + \lfloor\dfrac{R}{Q}\rfloor\)​，所以 \[ F(P, R, Q, N, X, Y) = Y^{\lfloor\dfrac{R}{Q}\rfloor}F(P, R \bmod Q, Q, N, X, Y) \]

若 \(P \geq Q\)​，则 \(f(i)= \lfloor \dfrac{(P \bmod Q)i+R}{Q}\rfloor + \lfloor\dfrac{P}{Q}\rfloor i\)​，记 \(f'(i)= \lfloor \dfrac{(P \bmod Q)i+R}{Q}\rfloor\)​ \[ \begin{aligned} F(P, R, Q, N, X, Y) &= X\prod_{i = 1}^N Y^{f'(i) - f'(i-1)}Y^{\lfloor\dfrac{P}{Q}\rfloor}X\\ &= X\prod_{i = 0}^{N - 1} Y^{f'(i+1) - f'(i)}Y^{\lfloor\dfrac{P}{Q}\rfloor}X\\ &= XF(P \bmod Q, (P \bmod Q) + R, Q, N - 1, Y^{\lfloor\dfrac{P}{Q}\rfloor}X, Y) \end{aligned} \] 若 \(P < Q\)，考虑交换 \(X, Y\)。

第 \(i\) 个 \(X\) 前有 \(f(i)\) 个 \(Y\)，设第 \(i\) 个 \(Y\) 前有 \(g(i)\) 个 \(X\)， \[ \begin{aligned} g(i) &= \sum_{j \geq 0} [f(j) < i+1]\\ &= \sum_{j \geq 0} \left[\lfloor \frac{Pj+R}{Q}\rfloor < i+1\right]\\ &= \sum_{j \geq 0} \left[ Pj+R\ < Qi+Q\right]\\ &= \sum_{j \geq 0} \left[j < \lfloor \frac{Qi + Q-R + P - 1}{P} \rfloor\right]\\ &= \lfloor \frac{Qi + Q-R + P - 1}{P} \rfloor \end{aligned} \] 但是末尾还有一些 \(X\)​ 后面没有 \(Y\)​，需要单独拿出来 \(X^{N+1 - \max g(i)}\)。​​

于是 \[ F(P, R, Q, N, X, Y) = F(Q, Q - R + P - 1, P, \lfloor \frac{PN + R}{Q} \rfloor-1, Y, X)X^{N+1 - \max g(i)} \]

复杂度为 \(O(T(S) \log N\log \min\{p, q\})\)，\(T(S)\) 为 \(S\) 上的乘法复杂度。

模板

S 即半群 \((S, \times)\) 的结构体，这里假定它是幺半群（否则可以加一个幺元进去），则 S() 代表幺元。

LL div(LL p, LL i, LL r, LL q) {
  return (p * i + r) / q; 
}
S cal(LL p, LL r, LL q, LL n, const S &x, const S &y) {
  if (n < 0) return S();
  if (r >= q) {
    return fpow(y, r / q) * cal(p, r % q, q, n, x, y);
  }
  if (p >= q) {
    return x * cal(p % q, p % q + r, q, n - 1, fpow(y, p / q) * x, y);
  }
  if (p == 0) {
    return fpow(x, n + 1);
  }
  LL m = div(p, n, r, q);
  return cal(q, q - r + p - 1, p, m - 1, y, x) * fpow(x, n + 1 - (!m ? 0 : div(q, m, p - r - 1, p)));
}

最后修改于 2022-06-02