Cod sursă (job #565862)

#include <bits/stdc++.h>

using namespace std;

ifstream in ("sqrt.in");
ofstream out ("sqrt.out");

typedef vector <int> Int;

const int B = 1000000000, X = 9;

string s;

void print(Int a) {
  if(a.empty()) {
    cout << "\n";
    return;
  }
  cout << a.back();
  for(int i = a.size() - 2; i >= 0; i--) {
    int x = a[i], c = (x == 0);
    while(x)
      c++, x /= 10;
    for(int j = 1; j <= X - c; j++)
      cout << 0;
    cout << a[i];
  }
  cout << "\n";
}

void rev(Int &a) {
  reverse(a.begin(), a.end());
}

Int get(long long n = 0) {
  vector <int> a;
  while(n)
    a.push_back(n % B), n /= B;
  return a;
}

Int operator + (Int a, Int b) {
  Int c;
  for(int i = 0, t = 0; i < (int)a.size() || i < (int)b.size() || t; i++, t /= B) {
    if(i < (int)a.size())
      t += a[i];
    if(i < (int)b.size())
      t += b[i];
    c.push_back(t % B);
  }
  return c;
}

bool operator <= (Int a, Int b) {
  if(a.size() != b.size())
    return (a.size() < b.size());
  for(int i = (int)a.size() - 1; i >= 0; i--) {
    if(a[i] != b[i])
      return (a[i] < b[i]);
  }
  return 1;
}

Int operator + (Int a, long long b) {
  return a + get(b);
}

Int operator * (Int a, int b) {
  long long t = 0;
  for(int i = 0; i < a.size() || t; i++, t /= B) {
    if(i < a.size())
      a[i] = (t += 1LL * a[i] * b) % B;
    else
      a.push_back(t % B);
  }
  return a;
}

bool check(Int p, Int a, int add, Int b) {
  return (p + a * (2 * add) + 1LL * add * add <= b);
}

Int sqrt(Int a) {
  Int ans = get(), nr = get(), p = get();
  int i = a.size() - 1;
  while(i >= 0) {
    for(int j = i; j > i - (1 + i % 2); j--) {
      nr = nr * B + a[j];
    }
    ans = ans * B;
    p = p * B;
    p = p * B;
    int st = 0, dr = B - 1, mid;
    while(st <= dr) {
      mid = (st + dr) >> 1;
      if(check(p, ans, mid, nr))
        st = mid + 1;
      else
        dr = mid - 1;
    }
    p = p + (1LL * dr * dr);
    p = p + ans * (2 * dr);
    ans = ans + dr;
    i -= 1 + i % 2;
  }
  return ans;
}

Int ans;

int main() {
  in >> s;
  for(int i = 0; i < s.size(); i++)
    ans = ans * 10 + (s[i] - '0');
  ans = sqrt(ans);
  out << ans.back();
  for(int i = ans.size() - 2; i >= 0; i--) {
    int x = ans[i], c = (x == 0);
    while(x)
      c++, x /= 10;
    for(int j = 1; j <= X - c; j++)
      out << 0;
    out << ans[i];
  }
  return 0;
}