你能找到解决这个问题的有效方法吗？

Question

给定以下递推关系：

C(0) = 0
C(n) = (C(n-1) + c * int(C(n-1) < u)) - u    // the int function converts a boolean to an integer.

约束：0 <= u <= c

你能找到一个有效的解决方案来找到第一个

n

(>= 1)（如果存在），其中

C(n)

= 0 吗？如果不存在这样的

n

，返回

-1

如果这样的

n

存在，一种蛮力方法是从一循环到无穷大，计算

C(n)

并在它为 0 时返回

n

。我们可以记住每次迭代的

C(n-1)

的值，所以我们不重新计算它。

Answer 1

直观上，函数按

c - u

稳定增加，直到达到或超过

u

，其中

u

从当前值中减去，并重复该过程。

首先要注意的是，当

u

“后退”时，它会以周期性的方式进行。第一次减去

u

后的值为

k * (c - u) - u

，其中整数

k

对应上一次迭代次数。该值以

(c - u)

为模等于

-u

。每次我们“后退”时，这都会“交错”：

-u mod (c - u)

.

接下来，我们想知道在达到零之前我们需要在序列中“后退”多少次。这本质上是在问我们在全部抵消之前“交错”序列多少次。在最坏的情况下（即我们的步长和交错是互质的），这等于我们的步长

(c - u)

。如果我们的步长和交错

-u

可能有一个共同的因素，我们必须除掉这个因素。这意味着我们在序列中“后退”的次数是：

(c - u) // gcd(c - u, stagger)

.

现在，我们需要计算序列中的总步数。后退步之间序列增加的次数不是恒定的 - 它最多会在两个不同的值之间变化（+/- 1）。然而，我们可以用不同的方式计算总步数，通过前向步骤增加的值减去后退步骤减去的值来表示函数的值：

fstep * (c - u) - bstep * u

。如果我们为前向步数解决这个问题，并添加到后步数，我们得到总步数，或者换句话说，

n

的值，其中

C(n)

等于

0

.

当然，如果

c == u

，结果就是

1

。我们可以立即返回它以避免被零除/取模。

将其放入（python）代码中：

from math import gcd

def solve(u, c):
    if c == u:
        return 1

    stagger = (-u) % (c - u)
    backsteps = (c - u) // gcd(c - u, stagger)
    steps = backsteps + backsteps * u // (c - u)
    return steps

我已经针对大约 2 万个随机选择的

(u, c)

对的天真暴力解决方案测试了此实现，其值范围为数千，结果完全匹配。我对它的正确性很有信心。

关于效率-最慢的部分是 GCD 计算，时间复杂度为

O(log(c)^2)

，所以总体来说它会非常快并且扩展性很好。