关于二元一次丢番图方程13x+5y=M在BST候选解下O(k)求解的逻辑困惑

Hey there! Let’s break down this confusion step by step. First, let’s recap the problem we’re tackling: we have the linear Diophantine equation 13x + 5y = M (where M is a given integer each time), and you’ve come across info saying that if we store a set of k unique integer candidate (x,y) pairs (with the correct solution included) in a Binary Search Tree (BST), we can find the valid solution pair in O(k) time. Let’s unpack why this works, and where that time complexity comes from.

First, let’s ground ourselves in the equation basics #

For a linear Diophantine equation like ax + by = c, solutions exist if and only if the greatest common divisor of a and b divides c. Here, gcd(13,5) is 1, which divides any integer M — so we know solutions exist for any input M. The general solution looks like:

x = x₀ + 5t
y = y₀ - 13t
where (x₀,y₀) is one particular solution, and t is any integer. Your "size-k candidate set" is almost certainly a finite subset of these solutions (probably constrained by positive integers, or some domain limits like x ≥ 0, y ≥ 0).

Why BST, and why O(k) time? #

You might be thinking: wait, BSTs are supposed to give O(log k) lookups, right? That’s true if you’re searching for a specific key you already know. But here, we’re not looking up a known value — we need to find which (x,y) pair in the set actually satisfies 13x + 5y = M for the current input M.

Here’s the typical process with a BST-stored candidate set:

• We have to traverse the entire BST (in-order, pre-order, whatever order works) to iterate through every candidate x (or y) in the set.
• For each candidate x, calculate what y would need to be to satisfy the equation: y = (M - 13x)/5.
• Check if that calculated y is an integer, and if the pair (x,y) exists in our candidate set (or if y is present in the corresponding y candidates, depending on how the BST is structured).

Since in the worst case, the correct pair is the last one we check, we end up visiting all k candidates — hence the O(k) time complexity. The BST doesn’t magically reduce this time because the valid y depends entirely on the current M, which changes every time we run the problem. We can’t precompute a direct lookup path in the BST for every possible M, so we have to verify each candidate.

Quick side note: Is BST the best structure here? #

Honestly, for this specific check, a BST doesn’t give you a time advantage over a regular array or linked list — you still end up checking all k elements in the worst case. The BST might be useful if you need to keep the candidates sorted for other parts of your problem (like inserting/deleting candidates efficiently), but for just finding the solution pair for a given M, it doesn’t change the worst-case time from O(k).

Does that clear up the confusion? The core idea is that even with a BST, the variable M means we can’t skip checking any candidates — we have to validate each one against the equation, leading to that O(k) runtime.

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