Cod sursă (job #109019)

#include <cstdio>
#include <cstring>

using namespace std;

const int MAXCIF = 3010 ;

struct numar
{
    char v[MAXCIF] ;
    int nrcif  ;

    numar ( int nr )
    {
        nrcif = 0 ;
        while ( nr != 0 )
        {
            v[nrcif++] = nr % 10 ;
            nr = nr / 10 ;
        }
        memset(v + nrcif ,0, sizeof(v) - nrcif );
    }

    numar aduna(numar &b)
    {
        numar c(0);
        int i , t = 0 ;
        for ( i = 0 ; i <= nrcif || i <= b.nrcif || t ; i++, t/=10 )
            c.v[i] = ( t += v[i] + b.v[i]) % 10 ;
        c.nrcif = i - 1 ;
        return c ;
    }

    numar inmulteste ( numar &b)
    {
        numar c(0) ;
        int i , j , t ;
        memset(c.v,0,sizeof(c.v));
        for ( i = 0 ; i < nrcif ; i++ )
        {
            for ( t = 0 , j = 0 ; j < b.nrcif || t ; j++ , t /= 10 )
                c.v[i+j] = ( t += c.v[i+j] +v[i] * b.v[j] ) % 10 ;
            if ( i + j > c.nrcif )
                c.nrcif = i + j ;
        }
        return c ;
    }

    numar imparte ( int b )
    {
        numar c(0) ;
        c.nrcif = nrcif ;
        int i , t = 0 ;
        for ( i = nrcif - 1 ; i >= 0 ; i-- , t %= b )
            c.v[i] = ( t = t * 10 + v[i] ) / b ;
        for ( ; c.v[0] > 1 && !c.v[c.nrcif - 1 ] ; --c.nrcif) ;
        return c ;
    }

    bool operator <= ( const numar &b) const
    {
        if ( nrcif < b.nrcif )
            return true ;
        if ( nrcif > b.nrcif )
            return false ;
        for ( int i = nrcif - 1 ; i >= 0 ; i-- )
        {
            if ( v[i] < b.v[i] )
                return true ;
            if ( v[i] > b.v[i] )
                return false ;
        }
        return true ;
    }
};

numar cif(0);

void citire()
{
    freopen("sqrt.in","r",stdin);
    freopen("sqrt.out","w",stdout);
    gets(cif.v);
    for ( int i = 0 ; cif.v[i] != 0 ; i++ )
    {
        cif.nrcif++;
        cif.v[i] -= '0' ;
    }
    char aux ;
    for ( int i = 0 , j = cif.nrcif - 1 ; i < j  ; i++ , j-- )
    {
        aux = cif.v[i] ;
        cif.v[i] = cif.v[j] ;
        cif.v[j] = aux ;
    }
}



numar cautare_binara()
{
    numar wanted(0);
    numar pas(1) ;
    numar doi(2);

    while ( pas.inmulteste(pas) <= cif )
        pas = pas.inmulteste(doi);

    numar aux(0);
    numar aux2(0);
    for (;!(pas.nrcif == 1 && pas.v[0]== 0 ) ;pas =  pas.imparte(2) )
    {
        aux = wanted.aduna(pas) ;
        aux2 = aux.inmulteste(aux) ;
        if ( aux2 <= cif )
            wanted = aux ;
    }
    return wanted ;
}

int main()
{
    citire();
    numar wanted(0);
    wanted = cautare_binara();
    for ( int i = wanted.nrcif - 1 ; i >= 0 ; i-- )
        printf("%d",(int)wanted.v[i]);
}