Длинная арифметика на олимпиадах по программированию

Речь пойдет сегодня о желании умножать целые числа, в которых количество цифр ограничено только… да ничем не ограничено, то есть о «Длинной арифметике» – так называют раздел олимпиадных задач по программированию, в которых требуется осуществлять арифметические действия с очень большими целыми числами. Многие сталкивались с ситуацией, когда обычный калькулятор не в состоянии точно вычислить, скажем, 20! (факториал), и причина банальна – табло калькулятора не в состоянии вместить все цифры ответа. Та же проблема и с калькулятором в компьютере. Даже тип данных int64, реализованный в языке Delphi, не может выполнять целочисленные арифметические действия с числами, которые превышают 263. Но иногда так хочется вычислить, скажем, произведение очень больших целых чисел, и хочется, чтобы ответ был точным, не приближенным, как скажем, это число: 1,414213562373095Е45.

Таким образом, умение написать программу для выполнения арифметических действий с очень большими целыми числами применимо не столько на олимпиадах по программированию, сколько пригодится для пытливого математика.

Олимпиадные задачи на длинную арифметику, на наш взгляд, заметно отличаются от остальных задач тем, что ученику можно приготовить несколько домашних заготовок – готовых процедур, которые можно применить на олимпиаде, столкнувшись с задачей длинной арифметики.