假设我们有一个值 n,我们必须找到 (a, b) [a < b] 对的数量,这些对的存在使得方程 a*x + b*y = n,至少有一个解。
因此,如果输入类似于 n = 4,那么输出将为 2,因为有效对是 (1, 2) 和 (1, 3)。
让我们看看以下实现以获得更好的理解 -
def divisors_gen(n): divs = [[1] for x in range(0, n + 1)] divs[0] = [0] for i in range(2, n + 1): for j in range(1, n // 我 + 1): divs[i * j].append(i) return [i[::-1] for i in divs] def solve(n): result = 0 d_cache = divisors_gen(n+1) for a in range(1, n): i = 1 s = set([]) while a*i < n: b = n - a*i for d in d_cache[b]: if d > a: if d not in s: result += 1 else: break s.add(d) i += 1 return result n = 4 print(solve(n))
4输出结果
2