Cod sursă (job #111234)

#include<cstdio>
#include<cctype>
#include<cstring>

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 inPlaceAdd(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 addHuge(huge*a,huge*b,huge*c) // WARNING: Rezultatul va fi trunchiat modulo 10^3000
{
	memset(c->v,0,4096);
	
	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 subtractHuge(huge*a,huge*b,huge*c)
{
	memset(c->v,0,4096);
	
	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 mulHuge(huge*a,int dig,huge*b)
{
	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 compareHuge(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];
		}
		
		cifre[0]=0;
		num++;
	}

	huge sqrt; intToHuge(&sqrt,0);
	huge te; intToHuge(&te,0);
	huge te2; intToHuge(&te2,0);
	huge p; intToHuge(&p,0);	

	for (int i=0;i<num;i+=2)
	{
		shift(&te,2);
		te.v[0]=cifre[i+1];
		te.v[1]=cifre[i];
		te.n=(te.n?te.n:2-(te.v[1]==0));
		
		shift(&sqrt,1);
		mulHuge(&sqrt,2,&te2);
		te2.v[0]=10;
		
		if (te2.n==0)
		{
			te2.n=1;
		}
		
		do
		{
			te2.v[0]--;
			mulHuge(&te2,te2.v[0],&p);
		} while(compareHuge(&p,&te)==1);
		
		fprintf(fout,"%d",te2.v[0]);
		
		sqrt.v[0]=te2.v[0];
		
		if(sqrt.n==0&&sqrt.v[0])
		{
			sqrt.n=1;
		}
		
		subtractHuge(&te,&p,&te2);
		copyHuge(&te,&te2);
	}

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