Cod sursă (job #572824)

#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()) {
    out << "\n";
    return;
  }
  out << 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++)
      out << 0;
    out << a[i];
  }
  out << "\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;
}

Int operator - (Int a, Int b) {
  Int c;
  for(int i = 0, t = 0; i < (int)a.size(); i++) {
    int x = a[i] - t;
    if(i < (int)b.size())
      x -= b[i];
    t = (x < 0);
    x += t * B;
    c.push_back(x);
  }
  while(c.size() > 1 && !c.back())
    c.pop_back();
  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;
}

Int sqrt(Int a) {
  Int ans = get(), rem = get(), tmp;
  vector <int> g;
  for(int i = 0; i < (int)a.size(); i += 2)
    g.push_back((i < (int)a.size() - 1 ? a[i + 1] * 10 : 0) + a[i]);
  reverse(g.begin(), g.end());
  for(auto &i : g) {
    tmp = ans;
    tmp = tmp * 20; tmp = tmp + 1;
    rem = rem * 100; rem = rem + i;
    int c = 0;
    while(tmp <= rem) {
      c++;
      rem = rem - tmp;
      tmp = tmp + 2;
    }
    ans = ans * 10; ans = ans + c;
  }
  return ans;
}

Int ans;

int main() {
  in >> s;
  for(int i = s.size() - 1; i >= 0; i--) {
    ans.push_back(s[i] - '0');
  }
  ans = sqrt(ans);
  print(ans);
  return 0;
}