根据自然数的余数序列求正整数

Question

有未知正整数 n，给出它对自然数 i（范围：1-300） 的余数 r 序列，求 n 。

即，已知 ri

r1 = n % 1
r2 = n % 2
r3 = n % 3
...
ri = n % i
...

求 n。

Answer 1

感谢 @萝卜 提示，采用中国剩余定理解法如下

import random
import math


def mod_inv(a, m):
    '''求 a 模 m 的数论倒数 n，即 (a*n) % m = 1'''
    a = a % m
    for x in range(1, m):
        if ((a * x) % m == 1):
            return x
    return 1


def is_prime(n):
    '''判断 n 是否为素数'''
    m = int(math.sqrt(n))
    for i in range(2, m + 2):
        if n % i == 0:
            return False
    return True


def all_prime_before(n):
    '''查找 n 以内的所有素数'''
    ps = []
    for i in range(2, n+1):
        if is_prime(i):
            ps.append(i)
    return ps


def resolve(ps, rs):
    # 限制猜数范围，不超过 8 位字节。
    k = 1
    ki = 0
    for i, v in enumerate(ps):
        if k*v > 0xffffffff:
            break
        k *= v
        ki = i
    print(f'+ 截取素数个数：{ki}, 积：{k}')

    ret = 0
    for idx, i in enumerate(ps):
        if idx > ki:
            break
        a = k // i
        b = mod_inv(a, i)
        ret = (ret + a * b * rs[idx]) % k
    return ret


def main():
    ps = all_prime_before(300)
    print('+ 素数列表：', ps)

    n = random.randint(0xffff, 0xffffffff)
    print('+ 随机数：', n)

    # 余数列表
    rs = []
    for i in ps:
        rs.append(n % i)

    m = resolve(ps, rs)
    print('+ 结果：', m)

    if m != n:
        raise Exception('结果不符')


if __name__ == '__main__':
    main()