Здравствуйте, сегодня я хотел бы рассказать об одном способе как можно упростить вычисления с длинной арифметикой. Допустим вам в задаче нужно посчитать некоторую величину, длину которой вы можете оценить сверху величиной len. Но возможно, чтобы посчитать эту величину требуется длинное умножение, сложение, вычитание, или еще какие-нибудь другие не простые операции. Предположим что ваша программа работает за T * len, тогда можно заменить это решение на другое, почти не использующее длинной арифметики и работающее за T * len / 9 + (len / 9) ^ 2. Чтобы сделать это воспользуемся Китайской теоремой об остатках. Выберем len / 9 некоторых различных простых чисел порядка 1000000000, и посчитаем ответ на нашу задачу по модулю каждого из данных простых за T * len / 9. Китайская Теорема об остатках утверждает, что существует единственное число меньшее чем произведение этих простых, у которого ровно такие остатки. Восстановить такое число не трудно, будем находить такое число по очереди для каждого префикса простых. На первом шаге наш ответ просто равен остатку. Далее на очередном шаге у нас есть некоторое число answer для предыдущего префикса и есть очередной остаток a и очередное простое число p[i]. Тогда достаточно решить уравнение: answer + x * p[0] * p[1] * ... * p[i — 1] = a(mod p[i]), такое x нетрудно найти, например, обратив p[0] * p[1] ... * p[i — 1] по модулю p[i]. Тогда новый answer будет равен answer + x * p[0] * p[1] * ... * p[i — 1]. Таким образом вместо всей длинной арифметики у нас осталось лишь умножение длинного числа на короткое. Более того этот способ может помочь если у вас были проблемы с памятью, так как если бы у вас раньше было памяти M * len, то сейчас можно обойтись M + len / 9. Сам я использовал этот способ в некоторых задачах и он действительно помогал мне избежать некоторых проблем. Ссылки на задачи: http://acm.timus.ru/problem.aspx?space=1&num=1467 http://acm.timus.ru/problem.aspx?space=1&num=1677