现在我可以提供
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)
