Cod sursă (job #216846)

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define BMAX 4096

struct Big {
	char v[BMAX];
	int n;
};

void init(Big* a, int num) // WARNING: Numarul trebuie sa fie pozitiv
{
	memset(a->v, 0, BMAX);
	int i = 0;
	while (num) {
		a->v[i++] = num % 10;
		num /= 10;
	}
	a->n = i;
}

void selfadd(Big* a, Big* b)
{
	int i = 0, carry = 0;
	for (i = 0; i <= a->n || i <= b->n; ++i) {
		a->v[i] += b->v[i] + carry;
		carry = a->v[i] / 10;
		a->v[i] -= 10 * carry;
	}
	a->n = (a->v[i - 1] ? i : i - 1);
}

void add(Big* a, Big* b, Big* c) // WARNING: Rezultatul va fi trunchiat modulo 10^3000
{
	memset(c->v, 0, BMAX);
	int i = 0, carry = 0, sum = 0;
	for (i = 0; i <= a->n || i <= b->n; i++) {
		sum = a->v[i] + b->v[i] + carry;
		c->v[i] = sum % 10;
		carry = sum / 10;
	}
	c->n = (c->v[i - 1] ? i : i - 1);
}

void sub(Big* a, Big* b, Big* c) // WARNING: a trebuie sa fie mai mare sau egal cu b
{
	memset(c->v, 0, BMAX);
	int i, carry = 0, sum = 0;
	for (i = 0; i < a->n; i++) {
		sum = a->v[i] - b->v[i] + carry;
		if (sum >= 0) {
			carry = 0;
			c->v[i] = sum % 10;
		} else {
			carry = -1;
			c->v[i] = (sum + 10) % 10;
		}
	}
	do {
		i--;
	} while (i >= 0 && c->v[i] == 0);
	c->n = i + 1;
}

void mul(Big* a, int dig, Big* b) // WARNING: dig trebuie sa fie cuprins strict intre 0 si 10!
{
	memset(b->v, 0, BMAX);
	b->n = 0;
	if (dig > 0) {
		int i = 0, carry = 0, sum = 0;
		for (i = 0; i <= a->n; ++i) {
			sum = a->v[i] * dig + carry;
			b->v[i] = sum % 10;
			carry = sum / 10;
		}
		b->n = (b->v[i - 1] ? i : i - 1);
	}
}

void shift(Big* a, int amount)
{
	if (a->n > 0) {
		int i;
		for (i = a->n + amount - 1; i >= amount; --i) {
			a->v[i] = a->v[i - amount];
		}
		for (i = amount - 1; i >= 0; --i) {
			a->v[i] = 0;
		}
		a->n += amount;
	}
}

void assign(Big* a, Big* b)
{
	memcpy(a->v, b->v, (a->n > b->n ? a->n : b->n));
	a->n = b->n;
}

int cmp(Big* a, Big* b)
{
	if (a->n < b->n) {
		return -1;
	} else if (a->n > b->n) {
		return 1;
	} else {
		int i;
		for (i = a->n - 1; i >= 0; --i) {
			if (a->v[i] != b->v[i]) {
				return (a->v[i] < b->v[i] ? -1 : 1);
			}
		}
		return 0;
	}
}

char digs[BMAX];

int main()
{
	FILE *fin, *fout;
	fin = fopen("sqrt.in", "r");
	fout = fopen("sqrt.out", "w");

	char read;
	int num = 0;
	while (isdigit(read = fgetc(fin))) {
		digs[num++] = read - '0';
	}
	if (num % 2) {
		int i;
		for (i = num; i > 0; i--) {
			digs[i] = digs[i - 1];
		}
		digs[0] = 0;
		num++;
	}
	/*for (int i = 0; i < num; i++) {
		printf("%d ", digs[i]);
	}*/

	Big S, Tmp, Aux, Par;
	init(&S, 0);
	init(&Tmp, 0);
	init(&Aux, 0);
	init(&Par, 0);

	int i;
	for (i = 0; i < num; i += 2) {
		shift(&Tmp, 2);
		Tmp.v[0] = digs[i + 1];
		Tmp.v[1] = digs[i];
		Tmp.n = (Tmp.n ? Tmp.n : 2 - (Tmp.v[1] == 0));

		shift(&S, 1);
		mul(&S, 2, &Aux);
		Aux.v[0] = 10;
		if (Aux.n == 0) {
			Aux.n = 1;
		}
		do {
			Aux.v[0]--;
			mul(&Aux, Aux.v[0], &Par);
		} while (cmp(&Par, &Tmp) == 1);
		fprintf(fout, "%d", Aux.v[0]);
		S.v[0] = Aux.v[0];
		if (S.n == 0 && S.v[0]) {
			S.n = 1;
		}
		sub(&Tmp, &Par, &Aux);
		assign(&Tmp, &Aux);
	}

	fclose(fin);
	fclose(fout);
	return 0;
}