Арифметика с большими целыми числами с использованием китайской теоремы об остатках
Это сделано Python
Предположим, что мы представляем сумму набора операций возведения в степень в виде списка кортежей, где каждый кортеж содержит два целых числа: основание и показатель степени. Например, список [(2,4),(3,5),(-6,3)] представляет собой сумму степеней 24 + 35 + (−6)3.
Реализовать функцию sumOfPowers(nes, ps) который принимает список из одного или нескольких кортежей nes (То есть, nes имеет форму [(a1,n1),...,(ak,nk)]) в качестве первого аргумента и список из одного или нескольких простых чисел ps (т. е. в форме [p1,...,pm]) в качестве второго аргумента. Функция должна возвращать правильный результат суммы мощностей, если выполняется следующее (например, на компьютере с неограниченной памятью и временем):
0 ≤ a1n1 +... + aknk
Вы можете предположить, что второй список содержит различные простые числа. Вы не можете предполагать, что числа в первом списке ввода имеют какие-либо конкретные шаблоны или отношения; они могут быть в любом порядке, они могут быть любого размера, и они могут иметь или не иметь общие факторы. Ваша реализация должна эффективно работать на очень больших входах