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

李毅
  • 5k

有未知正整数 n,给出它对自然数 i(范围:1-300) 的余数 r 序列,求 n 。

即,已知 ri

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

求 n。

回复
阅读 907
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()
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏