主页 / 问题 / 734145
Accepted
user259368
Asked:2020-10-22 14:31:59 +0000 UTC2020-10-22 14:31:59 +0000 UTC

找到数字 B 使得 A*B+A+B 对于给定的 A 和 N 可以被 N 整除

  • 772
f = open("input.txt", "r")
z = open("output.txt", "w+")
F = f.read()
A, N = map(int, F.split())
B = 0
с = 0
for B in range(10**9):
    if (A * B + A + B) % N == 0:
        с = 1
        break
if c != 1:
    B = -1
z.write(str(B))
f.close()
z.close()

给出了两个数字。A 和 N。我们需要找到一个 B 使得 (AB+A+B)%N=0（乘积和总和的和可以被 N 整除）。
时间限制为一秒。
迭代只适用于小数字。
如果没有这样的数字B，则输出-1。

如何快速检查所有数字B（B不大于10**9）？

python

1 个回答

  1. Best Answer

    无需枚举即可快速求解，只需求取反模 N 数即可。

    首先，我们重写表达式

    A * B + A + B = 0 (mod N) 
         ⇓
(A + 1) * (B + 1) = 1 (mod N) 
         ⇓ 
B = (A + 1)^(-1) - 1 (mod N)

    然后我们使用扩展欧几里得算法来求逆 A + 1 ，该算法几乎可以立即运行，不需要枚举。

    这是完整的 Python 代码（在线运行）：

    def inverse(a, n):
    (t, newt, r, newr) = (0, 1, n, a)
    while newr != 0:
        quotient = r // newr
        (t, newt) = (newt, t - quotient * newt) 
        (r, newr) = (newr, r - quotient * newr)
    if r > 1:
        raise ValueError("a is not invertible")
    if t < 0:
        t = t + n
    return t

def main():
    # A * B + A + B = 0 (mod N) <=> (A + 1) * (B + 1) = 1 (mod N) <=> B = (A + 1)^(-1) - 1 (mod N)
    A = 10
    N = 997
    B = 0

    try:
        B = (inverse(A + 1, N) - 1) % N
    except ValueError:
        B = -1

    print(B)

main()

    反演算法的收敛性是对数的，即 如果 A、B、N 大约为 2^k，则最大 2k+2 次迭代就足够了，即 对于 32 位最大数，最多 66 次迭代。看这里的证明。

    • 12

相关问题