Cod sursă (job #110716)

#include<stdio.h>
#include<string.h>
#include<ctype.h>

struct huge {
	char v[4096]; int n;
};

void intToHuge(huge* a, int num)
{
	memset(a->v,0,4096);
	int i=0;
	
	while(num)
	{
		a->v[i++]=num%10;
		num/=10;
	}
	
	a->n=i;
}

void add(huge* a, huge* 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 mulWithDig(huge* a, int dig, huge* b) // WARNING: dig trebuie sa fie cuprins strict intre 0 si 10!
{
	memset(b->v,0,4096);
	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(huge* 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 copyHuge(huge* a, huge* b)
{
	memcpy(a->v,b->v,(a->n>b->n?a->n:b->n));
	a->n=b->n;
}

int cmp(huge* a, huge* 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 cifre[4096];

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)))
	{
		cifre[num]=read-'0';
		num++;
	}
	
	if(num%2)
	{
		int i;
		for(i=num;i>0;--i)
		{
			cifre[i]=cifre[i - 1];
		}
		num++;
		cifre[0]=0;
	}

	huge N; intToHuge(&N, 0);
	huge radical; intToHuge(&radical, 0);
	huge radical2; intToHuge(&radical2, 0);
	huge t; intToHuge(&t, 0);
	huge one; intToHuge(&one, 1);

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

		copyHuge(&t,&radical2);
		while(cmp(&t,&N)<1)
		{
			copyHuge(&radical2,&t);
			mulWithDig(&radical,2,&t);
			add(&t,&one);
			add(&t,&radical2);
			radical.v[0]++;
			radical.n+=(radical.n==0);
		}
		fprintf(fout,"%d",--radical.v[0]);
	}

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