16 Длинная арифметика

Данный листочек посвящен проблеме представления в памяти компьютера длинных целых чисел и операциям над ними.

Длинные числа удобно хранить в виде последовательностей цифр в системе счисления с основанием 10 или 10000. С основанием 10 удобнее работать, в то время как основание 10000 позволяет экономнее расходовать память и в несколько раз быстрее выполнять операции.

Для хранения длинного целого числа создадим соответствующую структуру:

     struct Longint
     {
         int sign;       // Знак числа, например, 1, 0, -1
         int size;       // Количество цифр в числе
         short * digits; // Массив с цифрами
         int allocated;  // Размер памяти, выделенной под хранение цифр
     };

Удобно, когда цифры хранятся в обратном порядке: digits[0] – самая младшая (правая) цифра, digits[size-1] – самая старшая цифра.

В поле allocated будем хранить размер массива digits, то есть максимально возможное количество цифр в числе. При этом всегда должно быть выполнено условие allocated>=size. Если же возникает необходимость увеличить величину массива, то необходимо вызвать специальный метод, который будет увеличивать размер массива digits.

Первоначальная память для массива digits выделяется в специальном методе, называемом конструктором, который автоматически вызывается при создании объекта. Имя метода-конструктора совпадает с именем структуры. Конструктор не возвращает никакого значения (даже void)! Пример конструктора, который создает длинное число и присваивает ему значение 1:

     Longint()
     {
         allocated=10; // По умолчанию выделяем память на 10 разрядов
         sign=1;
         digits=new short[allocated];
         size=1;
         digits[0]=1;
     }

В свою очередь выделенная память в конструкторе должна быть освобождена в деструкторе: методе, который вызывается при удалении объекта. Имя деструктора начинается со знака тильды, за которым идет имя класса. Деструктор не принимает параметров и не возвращает значение:

     ~Longint()
     {
         delete digits;
     }

Упражнения

Разработайте самостоятельно структуру для работы с длинными целыми числами. Используйте основание системы счисления 10000 для внутреннего представления. Реализуйте операции ввода-вывода:

     istream & operator >> (istream &, Longint &);
     ostream & operator << (ostream &, const Longint &);

Реализуйте копи-конструктор

     Longint(const Longint &);

Реализуйте конструктор построения длинного числа из короткого:

     Longint(int);

Реализуйте оператор присваивания:

     Longint & operator=(const Longint &);

Реализуйте арифметические операторы сложения и вычитания:

     Longint  operator+  (const Longint &, const Longint &);
     Longint& operator+= (      Longint &, const Longint &);
     Longint  operator-  (const Longint &, const Longint &);
     Longint& operator-= (      Longint &, const Longint &);

Реализуйте операторы сравнения, умножения, деления и т.д.

Во всех задачах этого листка подразумевается, что все входные числа являются неотрицательными целыми не превосходящими 10¹⁰⁰, если особо не оговорено иное.

Входные данные хранятся в файле input.txt, выходные данные в файле output.txt.

1. (A) Дано чиcло n. Выведите число n+1.
2. (B) Даны два числа. Выведите знак <, если первое число меньше второго, знак >, если первое больше второго или знак =, если числа совпадают.
3. (C) Даны два числа. Выведите их сумму.
4. (D) Даны два числа, второе из них не превышает первого. Выведите их разность.
5. (Е) Даны два числа. Выведите их разность (учтите, что может получиться отрицательный результат).
6. (F) Даны два числа, второе из них не превышает 9999. Выведите их произведение (реализуйте умножение длинного числа на короткое с основанием 10000).
7. (G) Даны два числа. Выведите их произведение.
8. (H) Дано одно число и число от 1 до 9. Выведите частное от деления первого на второе.
9. (I) Дано одно число и число от 1 до 9. Выведите остаток от деления первого на второе.
10. (J) Дано одно число и число от 1 до 9999. Выведите частное от деления первого на второе.
11. (K) Дано одно число и число от 1 до 9999. Выведите остаток от деления первого на второе.
12. (L) Дано два числа. Выведите частное от деления первого на второе.
13. (M) Дано два числа. Выведите остаток от деления первого на второе.
14. (N) Дано число N не превосходящее 3000. Выведите его факториал.
15. (O) Даны два числа N и P, 1≤N≤10⁹, 1≤P≤100. Вычислите N^N mod 10^P.
16. (P) Дано число A. Извлеките из него квадратный корень: найдите такое наибольшее целое число X, что X²≤A.