Привет, Codeforces!

Когда говорят про языки программирования со встроенной реализацией длинной арифметики, обычно говорят о таких языках, как Java или Python. Сегодня я расскажу про длинку в языке Pascal, а, точнее, в его реализации Free Pascal Compiler.

Простейший код, который читает два "длинных" числа и складывает их, выглядит так:

program sum;

{$Mode Delphi}

uses
  gmp;

var
  sa, sb: string;
  a, b: MPInteger;
begin
  readLn(sa);
  readLn(sb);
  a := sa; b := sb;
  writeLn(string(a + b));
end.

Модуль gmp содержит все классы и операторы дя работы с "длинными" числами.

Как он работает? Этот модуль содержит заголовки функций, импортируемые из GNU Multiprecision Library. Программа и библиотека связываются динамически, поэтому для работы программы необходимо, чтобы эта библиотека была установлена. К счастью, в большинстве дистрибутивов Linux она установлена по умолчанию и поэтому может быть использована в таких системах, как ejudge и Яндекс.Контест. В тестирующих системах на Windows библиотека не установлена, поэтому такая штука не сработает.

Для удобства работы в модуле реализована объектно-ориентированная обёртка над функциями libgmp, для которой перегружены все необходиые операторы (да-да, во Free Pascal есть перегрузка операторов!)

Что еще примечательно, в libgmp реализовано быстрое извлечение целочисленного квадратного корня. Поэтому можно написать очень простой, быстрый и короткий код на задачу F с заочного тура Открытки.

program F;

{$mode objfpc}{$h+}
{$optimization LEVEL3}

uses gmp;

var
  num: string;
  mpNum: MPInteger;
  root, rem: MPInteger;
begin
  readLn(num);
  mpNum := num;
  mpNum := mpNum - 1;
  z_sqrtrem(root, rem, mpNum);
  if rem < root then begin
    writeln(string(rem + 1));
  end else begin
    writeln(string(2 * root + 1 - rem));
  end;
end.