求递推关系中首个使C(n)=0的n值的高效解法

问题回顾 #

给定递推关系：

C(0) = 0
C(n) = (C(n-1) + c * int(C(n-1) < u)) - u    // int函数将布尔值转为整数（真为1，假为0）

约束条件：0 <= u <= c

要求找到首个满足C(n)=0的n值（n≥1），若不存在则返回-1。

高效解法 #

无需迭代计算，通过数论分析直接得出结果：

情况1：u = 0 或 u = c #

直接返回1。

• 当u=0时，C(1)=0 + c*int(0<0) - 0 = 0；
• 当u=c时，C(1)=0 + c*int(0<c) - c = 0。

情况2：0 < u < c #

计算u和c的最大公约数d = gcd(u, c)，返回c // d。

推导依据 #

令u = d*u'，c = d*c'，此时gcd(u', c')=1，且c-u = d*(c'-u')。
我们需要找到最小的n，使得累积操作的总变化为0：
x*(c-u) - y*u = 0
代入化简得x*(c'-u') = y*u'，由于u'和c'-u'互质，最小正整数解为x=u'、y=c'-u'，总次数n=x+y = c' = c/d，这就是首个回归0的n值。

示例验证 #

• 例：u=2，c=6 → d=gcd(2,6)=2 → n=6//2=3
  计算序列：C(0)=0 → C(1)=4 → C(2)=2 → C(3)=0，符合预期。
• 例：u=1，c=5 → d=1 → n=5
  计算序列：C(0)=0 → C(1)=4 → C(2)=3 → C(3)=2 → C(4)=1 → C(5)=0，符合预期。

代码实现 #

import math

def find_first_zero_n(u, c):
    if u == 0 or u == c:
        return 1
    return c // math.gcd(u, c)

内容的提问来源于stack exchange，提问作者Samuel Okechukwu