Cod sursă (job #151568)

#include <stdio.h>
#include <stdlib.h>
#define MAXNREZ 3000
int rez[MAXNREZ],pas[2*MAXNREZ],v[MAXNREZ*2],n[MAXNREZ],v1[MAXNREZ*2];
int npas,nrez;
inline int getmax(int a,int b){
    if(a>b) return a;
    return b;
}
inline int adun(){
    int i,t=0,max=getmax(npas,nrez);
    for(i=0;i<max;i++){
        t=t+pas[i]+rez[i];
        v[i]=t%10;
        t/=10;
    }
    if(t>0)
        v[max++]=t;
    return max;
}
inline int prod(int nv){
    int i,j,t;
    for(i=0;i<=2*nv;i++)
        v1[i]=0;
    for(i=0;i<nv;i++){
        t=j=0;
        while(j<nv){
            v1[i+j]=(t+=v1[i+j]+v[i]*v[j])%10;
            t/=10;
            j++;
        }
        if(t>0)
            v1[i+nv]=t;
    }
    i=nv*2;
    while(v1[i]==0)
        i--;
    i++;
    for(j=0;j<i;j++)
        v[j]=v1[j];
    return i;
}
inline int comp(int *v1,int *v2,int nv,int nn){
    int i=nv-1;
    if(nv>nn)
        return 0;
    else
        if(nn>nv)
           return 1;
        else{
            while(i>=0&&v1[i]==v2[i])
                 i--;
            if(i==-1)
                return 1;
            else
                if(v1[i]>v2[i])
                   return 0;
                else
                    return 1;
        }
}
int main(){
    FILE*fi,*fout;
    int i,nn,nv,t,j,flag,aux,max;
    char a;
    fi=fopen("sqrt.in" ,"r");
    fout=fopen("sqrt.out" ,"w");
    a=fgetc(fi);
    nn=0;
    while(a>='0'&&a<='9'){
        n[nn++]=a-'0';
        a=fgetc(fi);
    }
    i=nn-1;
    j=0;
    while(i>j){
        aux=n[i];
        n[i]=n[j];
        n[j]=aux;
        i--;j++;
    }
    pas[0]=flag=npas=1;
    while(flag){
        t=0;
        for(j=0;j<npas;j++){
            t=t+pas[j]*2;
            pas[j]=t%10;
            t/=10;
        }
        if(t>0)
            pas[npas++]=t;
        flag=comp(pas,n,npas,nn);
    }
    nrez=0;
    while(npas>0){
        nv=prod(adun());
        if(comp(v,n,nv,nn)==1){
            t=0;
            max=getmax(nrez,npas);
            for(i=0;i<max;i++){
                rez[i]=t+pas[i]+rez[i];
                t=rez[i]/10;
                rez[i]=rez[i]%10;
            }
            if(t>0)
                rez[max++]=t;
            nrez=max;
        }
        t=0;
        for(i=npas-1;i>=0;i--){
            t=t*10+pas[i];
            pas[i]=t/2;
            t=t%2;
        }
        if(pas[npas-1]==0)
            npas--;
    }
    for(i=nrez-1;i>=0;i--)
        fprintf(fout,"%d" ,rez[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}