Hello, Codeforces!

When we talk the languages with built-in big integer implementation, usually such languages as Java or Python are mentioned. Now I'll tell you about long arithmetic implementation in Pascal (more precisely, in the Free Pascal Compiler).

The simplest code, which reads two big integers and outputs their sum, looks like this:

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 unit contains all the classes and operators to work with big integers.

How does it work? This unit contains bindings for GNU Multiprecision Library. The program and the library are linked dynamically, so, to make the program work this library is required to install. Luckily, many Linux distros install libgmp by default and so this trick can be used in the testing systems like ejudge or Yandex.Contest. Testing systems on Windows don't have this library, so this thing won't work.

For convenience the unit implements an object-oriented wrapper for libgmp functions, for which all the operators are overloaded (yes, Free Pascal supports operator overloading!)

What is also remarkable, libgmp has implementation for calculating fast integer square root. So here is a short implementation for problem F for elimination to Moscow Open Olympiad (the website by the link is in Russian and , unfortunately, I cannot find the English version of the statements).

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.