找到最小迭代次数以达到一定的总和

找到最小迭代次数以达到一定的总和

现在我可以提供

O(nlogn)

解决方案。

该方法似乎是最大公约数

使用

f(x, y)

表达此状态的最小迭代次数。可以通过

f(x-y, y)

if

x>y

或

f(x,y-x)

if
达到此状态

x<y

。我们可以看到达到状态的方式

(x,y)

是唯一的，我们可以

O(logn)

像gcd那样计算它。

答案是

min( f(n, i) | 1 <= i < n)

如此复杂

O(nlogn)

python代码：

def gcd (n, m):    if m == 0:        return n    return gcd (m, n%m)def calculate (x, y):    if y == 0:        return -1    return calculate (y, x%y) + x/ydef solve (n):    x = 0    min = n    for i in xrange (1, n):        if gcd (n, i) == 1: ans = calculate (n, i) if ans < min:     min = ans     x = i    print minif __name__ == '__main__':    solve (5)