基于中国剩余定理的大整数算法

Question

这是由Python完成的

假设我们将一组求幂运算的总和表示为一个元组列表，其中每个元组包含两个整数：基数和指数。例如，列表[(2,4),(3,5),(-6,3)]表示幂之和2⁴+3⁵+（−6）³。在

实现一个函数sumOfPowers(nes, ps)，该函数将一个或多个元组的列表nes（即，nes的形式为[(a1,n1),...,(ak,nk)]）作为其第一个参数，并将一个或多个素数ps（即[p1,...,pm]）的列表作为其第二个参数。只要满足以下条件，函数应返回正确的幂和结果（例如，在内存和时间不受限制的计算机上）：

0 ≤ a1ⁿ¹ + ... + ak^nk < p1 ⋅ ... ⋅ pm

你可以假设第二个列表包含不同的质数。您可能不认为第一个输入列表中的数字具有任何特定的模式或关系；它们可以是任何顺序，可以是任意大小，并且可以也可以不共享因子。您的实现必须在非常大的输入上高效地工作