LintCode 1328. 翻倍 Python算法

描述

给定数字 AA 和 BB 以及系数 pp 和 qq 。
每次操作可以将 AA 变成 AA + pp 或者将 pp 变成 pp * qq。
返回最少变化次数使得 BB <= AA

说明

1≤A≤1e ^​9
​​
1 \leq B \leq 1e^91≤B≤1e ^​9
​​
1 \leq p \leq 1e^91≤p≤1e ^​9
​​
2 \leq q \leq 102≤q≤10

样例

- 示例 1:
输入:
A = 2
B = 10
p = 1
q = 2
输出: 4
解释：通过三次变换之后，p = 8, 然后 A + p = 10，所以最终返回4.

- 示例 2:
输入:
A = 2
B = 13
p = 8
q = 4
输出: 2
解释：通过一次变换之后，p = 32, 然后 A + p = 34，所以最终返回2.

解析

class Solution:
    def DoubleChange(self, A, B, p, q):
        count = 0
        while A + p < B:
            p = q * p
            count += 1
        return count + 1

运行结果