中国剩余定理

Question

中国剩余定理告诉我们，我们总是可以找到一个在不同素数模下产生任何所需余数的数字。您的目标是编写代码，以便在多项式时间内输出这样的数字。最短代码获胜。

例如，假设我们被赋予了这些约束：

n \equiv 2 \mod 7

n \equiv 4 \mod 5

n \equiv 0 \mod 11

一个解决方案是n=44。第一个约束是满足的，因为44 = 6\times7 + 2，所以44在除以7时有剩余的2，因此是44 \equiv 2 \mod 7。另外两个制约因素也得到了满足。还有其他解决方案，如n=814和n=-341。

输入

一个非空的对(p_i,a_i)列表，其中每个模p_i是一个不同的素数，而每个目标a_i是范围0 \le a_i < p_i中的一个自然数。您可以以任何方便的形式接受输入；它实际上不必是一对的列表。您可能不会假设输入是排序的。

输出

一个整数n，使每个索引i的n \equiv a_i \mod p_i。它不一定是最小的这样的值，而且可能是负的。

多项式时间限制

为了防止只尝试n=0, 1, 2, \dots之类的廉价解决方案，您的代码必须在输入长度的多项式时间内运行。注意，输入中的数字m有长度Θ(\log m)，因此m本身在长度上不是多项式。这意味着您不能计数到m或执行m次数的操作，但是可以计算值上的算术操作。

您可能不会使用效率低下的输入格式(如一元)来绕过这一问题。

其他禁令

不允许内建做以下操作:实现中国剩余定理、求解方程或因子数。

您可以使用内置查找mods和模块加法，减法，乘法和指数(与自然数指数)。您不能使用其他内置的模块操作，包括模逆、除法和订单查找。

测试用例

这些给出了最小的非负解。你的答案可能不一样。如果直接检查输出是否满足每个约束，可能会更好。

[(5, 3)] 
3

[(7, 2), (5, 4), (11, 0)]
44

[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
1770977011

[(982451653, 778102454), (452930477, 133039003)]
68121500720666070

Answer 1

Ruby，129

同志们，看来Ruby解决方案必须更长一些，因为如果不加载openssl库并进行到OpenSSL::BN的转换，就无法获得模块化幂运算。不过，写起来还是很有趣的：

require("openssl")
z=eval(gets)
x=1
z.map{|a,b|x*=a}
s=0
z.map{|a,b|e=a.to_bn;s+=(x/a).to_bn.mod_exp(e-2,e).to_i*b*x/a}
puts(s)

Answer 2

Python 2，61

n=P=1
for p,a in input():n+=P*(a-n)*pow(P,p-2,p);P*=p
print n

这使用了其他答案使用的产品建设的一个变体。

其思想是在约束上循环，并更新解决方案n以满足当前约束，而不影响前面的约束。为此，我们跟踪到目前为止所见素数的乘积P，并观察到添加P的倍数对任何已经见过的素数都没有任何影响。

因此，我们只需要通过添加正确的n倍数来更改n%p == a以满足P。我们求解系数c：

(n + P*c) % p == a

这需要c = (a-n) * P^(-1)，其中逆的是模p。正如其他人所指出的，逆可以用Fermat的小定理作为P^(-1) = pow(P,p-2,p)来计算。所以，c = (a-n) * pow(P,p-2,p)，我们用n+= P * (a-n) * pow(P,p-2,p)更新n。