You are given three integers: A, B, and N. Your task is to determine whether it is possible to reach the value N starting from either A or B using one of the following operations:
- Replace
AwithA + B. - Replace
BwithA + B. If it is possible to reachN, print the minimum number of operations required. If it is not possible printNOT POSSIBLE.
Constraints
-10000000000 ≤ A, B, N ≤ 10000000000
Example 1
Input:
A = 1
B = 2
N = 5Output:
2Explanation: (1, 2) -> (2, 3) -> (3, 5)
Example 2
Input:
A = -1
B = 0
N = 5Output:
"NOT POSSIBLE"Explanation:
(-1, 0) -> (-1, 0)
States are either remain unchanged or produce negative value for both A and B.
解法
数学性质：从 (A, B) 经过一次操作得到 (A+B, B) 或 (A, A+B)。等价于斐波那契式扩展。逆向思考：从 (A, B) 出发用斐波那契式倍增搜索 N。若 A == N 或 B == N 返回 0；否则不断生成下一项 c = A + B，并贪心：每步用更小项替换 (a, b) = (b, a+b)，直到出现 N 或下一项已超过 N 的可达边界。复杂度 O(log N)，空间 O(1)。
def reach_a_given_number(A: int, B: int, N: int) -> str:
if A == N or B == N:
return "0"
if A + B <= max(A, B):
return "NOT POSSIBLE"
a, b = A, B
steps = 0
LIMIT = 10**12
while abs(a) <= LIMIT and abs(b) <= LIMIT:
c = a + b
steps += 1
if c == N:
return str(steps)
if c > N and a > 0 and b > 0:
return "NOT POSSIBLE"
a, b = b, c
return "NOT POSSIBLE"class Solution {
String reachAGivenNumber(long A, long B, long N) {
if (A == N || B == N) return "0";
if (A + B <= Math.max(A, B)) return "NOT POSSIBLE";
long a = A, b = B;
int steps = 0;
long LIMIT = (long) 1e12;
while (Math.abs(a) <= LIMIT && Math.abs(b) <= LIMIT) {
long c = a + b;
steps++;
if (c == N) return Integer.toString(steps);
if (c > N && a > 0 && b > 0) return "NOT POSSIBLE";
a = b;
b = c;
}
return "NOT POSSIBLE";
}
}class Solution {
public:
string reachAGivenNumber(long long A, long long B, long long N) {
if (A == N || B == N) return "0";
if (A + B <= max(A, B)) return "NOT POSSIBLE";
long long a = A, b = B;
int steps = 0;
const long long LIMIT = (long long) 1e12;
while (abs(a) <= LIMIT && abs(b) <= LIMIT) {
long long c = a + b;
steps++;
if (c == N) return to_string(steps);
if (c > N && a > 0 && b > 0) return "NOT POSSIBLE";
a = b;
b = c;
}
return "NOT POSSIBLE";
}
};