TLE: csu 1211 정수 제곱 연습

/*       */
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# include <math.h>
# include <time.h>

# define MAXN 1001

void bigN_sqrt(char *s);
int bigN_cmp(char *a, char *b, int lim);
void bigN_mul(char *a, int k, int lim);
void bigN_add(char *a, int k);
void bigNN_minus(char *a, char *b, int lim);

char str[MAXN];

int main()
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    while (~scanf("%s", str))
        bigN_sqrt(str);

     printf("time cost %.3lfs.
", (double)clock()/CLOCKS_PER_SEC);
    return 0;
}

int bigN_cmp(char *a, char *b, int lim)
{
    int i;
    for (i = lim-1; i >= 0; --i)
        if (a[i] < b[i]) return 1;
        else if (a[i] > b[i]) return -1;
    return 0;
}
void bigN_mul(char *a, int k, int lim)
{
    int i, tmp, c;
    for (c=i=0; i < lim; ++i) {
        tmp = a[i]*k + c;
        c = tmp / 10;
        a[i] = tmp - 10*c;
    }
}
void bigN_add(char *a, int k)
{
    int i = 0;
    while (k > 0) {
        a[i++] += k%10;
        k /= 10;
    }
}
void bigNN_minus(char *a, char *b, int lim) // b = b - a;
{
    int i, tmp, c;
    for (c=i=0; i < lim; ++i) {
        tmp = b[i] - a[i] + c;
        c = (tmp<0 ? -1:0);
        b[i] = (tmp+10) % 10;
    }
}
void bigN_sqrt(char *s)
{
    short int i, k, slen;           //         
    char res[MAXN];                 //     
    char cur[MAXN];                 //     
    char tmp[MAXN];
    int lim;

    memset(res, 0, sizeof(res));
    memset(cur, 0, sizeof(cur));

    lim = slen = strlen(s);
    if (slen < 18) {
        printf("%.0lf
", sqrt(atof(s)));
        return;
    }
    if (slen & 0x1) {
        k = -1;
        cur[0] = s[0] - 48;
    } else {
        k = 0;
        cur[1] = s[0] - 48;
        cur[0] = s[1] - 48;
    }
    while (1) {
        i = 0;
        while (1) {
            ++i;
            memcpy(tmp, res, MAXN);
            bigN_mul(tmp, i*20, lim);
            bigN_add(tmp, i*i);
            if (-1 == bigN_cmp(tmp, cur, lim)) break;     // break until tmp > cur;
        }
        --i;
        printf("%d", i);

        memcpy(tmp, res, MAXN);     //cur -= res*i*20+i*i;
        bigN_mul(tmp, i*20, lim);
        bigN_add(tmp, i*i);
        bigNN_minus(tmp, cur, lim);

        bigN_mul(res, 10, lim);        // res = res*10+i;
        bigN_add(res, i);

        k += 2;
        if (k >= slen) break;
        else {
            bigN_mul(cur, 100, lim);
            bigN_add(cur, ((s[k]-48)*10+(s[k+1]-48)));
        }
    }
    printf("
");
}