摘要
Title: 第十三届蓝桥杯省赛 B. 寻找整数
Tag: 最小公倍数、数论、中国剩余定理
Memory Limit: 64 MB
Time Limit: 1000 ms

B. 寻找整数

题意

找一个不超过 10的17次方的正整数 n，这个n是除以 2 至 49 后的余数已经是给定了的，求这个正整数最小是多少？
思路

之前写过一个中国剩余定理的解法，Link，下面给出一个更通俗易懂的解法

给出结论：若 $x \% m1 = a1, x \% m2 = a2$ ，那么下一个满足这个条件的数为 $x + lcm(m1, m2)$ （该结论可以推广为 $n$ 项）

那么对于这个题
- 当模数 $m1$ 满足条件时，就更新一下 $LCM = lcm(LCM, m1)$
- 当模数 $m1$ 不满足条件时，就让 $x$ 一直加到满足条件为止
ps: 只适用于有解的情况

代码

'''
Author: NEFU AB-IN
Date: 2022-04-09 10:04:11
FilePath: \Contest\tempCodeRunnerFile.py
LastEditTime: 2022-04-12 11:26:23
'''
def gcd(a, b):
    return gcd(b, a % b) if b else a


d = [
    0, 0, 1, 2, 1, 4, 5, 4, 1, 2, 9, 0, 5, 10, 11, 14, 9, 0, 11, 18, 9, 11, 11,
    15, 17, 9, 23, 20, 25, 16, 29, 27, 25, 11, 17, 4, 29, 22, 37, 23, 9, 1, 11,
    11, 33, 29, 15, 5, 41, 46
]

# ans为结果，id为模数，lcm初值为2（即一开始的模数为2）

id = 2
while id <= 49:
  if id == 2:
      lcm, ans = id, d[id]
  if ans % id == d[id]:
      lcm = lcm // gcd(lcm, id) * id
      id += 1
  else:
      ans += lcm

print(ans)

B. 寻找整数

题意

思路

代码