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

В основном мы будем рассматривать работу с целыми числами. Для хранения длинного числа можно использовать целочисленный массив, где в качестве элемента массива будет одна цифра числа. В 1м элементе массива будем хранить последнюю цифру числа, во 2м - предпоследнюю и т.д. до последней цифры. В 0м элементе можно хранить общее количество цифр в числе. В простейшем случае, для хранения числа 154 достаточно будет использовать следующую запись:

  const maxsize=100;
  int a[maxsize];
  a[0]=3; a[1]=4; a[2]=5; a[3]=1;

Элементом массива может быть не одна цифра, возможно использовать один элемент для хранения 4х цифр, т.к. мы понимаем, что на современных ЭВМ все операции как минимум 32-разрядные, поэтому время на сложение двух цифр такое же как и на сложение чисел, состоящих из 4х цифр. Поэтому часто используют порядок системы счисления base=10000 и фактически длинные числа хранятся как бы в 10000-й системе счисления, это позволяет увеличить скорость выполнения операций над ними в 3-4 раза.

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

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

  void readlong(int *a){
    int i;
    string s;
    read(s);
    a[0]=len(s);
    for i=1..a[0]{
      a[a[0]-i+1]=ord(s[i])-48;
    }
  }

  void writelong(int *a){
    for i=a[0]..1{
      write(a[i]);
    }
  }

Так же часто возникает необходимость сравнивать длинные числа. Опишем следующую функцию, которая будет возвращать 0 в случае равенства чисел, -1 когда первое число меньше второго и 1 когда первое больше:

  int complong(int *a, int *b){
    if (a[0] < b[0]) return -1;
    if (a[0] > b[0]) return 1;
    for i=a[0]..1{
      if(a[i] < b[i]) return -1;
      if(a[i] > b[i]) return 1;
    }
    return 0;
  }

Список задач