计算机系菜鸟一个..  初次开独立博客,请多多指教!


这题弄了我好久,终于比标程还快了.. 高精压位+二分..

算压位后的数字的长度是在大脑发胀,所以写得有点长,所以main函数也很乱了..

题目 简单问题 源程序名 easy.???(pas|c|cpp)
输入文件名 easy.in
输出文件名 easy.out
时间限制 1s/testcase
空间限制 32MB
– 问题描述 大家都喜欢在pascal中使用sqrt函数。现在你需要自己写一个sqrt函数:对于给定的正整数X(不超过1000位),计算sqrt(X)的整数部分。
– 输入数据 一行,X
– 输出数据 一行,代表sqrt(X)的整数部分
– 样例输入 1234
– 样例输出 35

#include< stdio.h >
#include< string.h >
char ss[1009];
long a[1009],l[1009],r[1009],b[1009],zz;
double c[1009];//a为目标,l为左,r为右,c为临时,b为当前
void erfen()
{
//memset(b,0,sizeof(b));
    int len=zz,i;
    for (i=0;i < =zz;i++)
        b[i]=l[i]+r[i];
    for (i=len;i > =0;i--)
    {
        if (b[i]%2)
        {
            b[i-1]+=10000;
        }
        b[i]/=2;
    }
    for (i=0;i < =zz;i++)
    {
        if (b[i]>9)
        {
            b[i+1]+=b[i]/10000;
            b[i]%=10000;
        }
    }
}
bool pandeng()
{
    int i=zz;
    while (l[i]==r[i])i--;
    if (i==0)
    {
        if (r[i]-l[i]==1)return true;
        else return false;
    }
    else return false;
}
bool pan()
{
    memset(c,0,sizeof(c));
    int k,i,j;
    for (i=0;i < =zz;i++)
    {
        for (j=0;j < =zz;j++)
        {
            c[i+j]+=b[i]*b[j];
        }
    }
    for (i=0;i < =zz*2;i++)
    {
        if (c[i]-9999.0>1e-6)
        {
            k=c[i]/10000.0;
            c[i+1]+=k;
            c[i]-=k*10000.0;
        }
    }
    int x=zz*2;
    if (c[zz*2+1])
    {
        x=zz*2+1;
    }
    for (i=x;i > =0;i--)
    {
        if (c[i] > a[i])return true;
        else if (c[i] < a[i])return false;
    }
    return false;
}
void copy(long *s1,long *s2)
{
    int i;
    for (i=0;i < =zz;i++)
    {
        s1[i]=s2[i];
    }
}
int main()
{
    FILE *fp,*fo;
    fp=fopen("easy.in","r");
    fo=fopen("easy.out","w");
    fgets(ss,1009,fp);
    int len=strlen(ss);
    int i,j;
    if (ss[len-1]=='\n')
    {
        ss[len-1]='\0';
        len--;
    }
    int chang=len%4,ttmmpp=len/4;
    for (i=0;i < chang;i++)
    {
        a[len/4]*=10;
        a[len/4]+=ss[i]-'0';
    }
    for (i=0;i < ttmmpp;i++)
    {
        a[ttmmpp-i-1]=(ss[i*4+chang]-'0')*1000+(ss[i*4+1+chang]-'0')*100+(ss[i*4+2+chang]-'0')*10+ss[i*4+3+chang]-'0';
    }
    zz=(len/2)/4;
    if (len%4==0)zz--;
    if (len%4!=0)
    {
        int ccc=((len%2==0)?len/2:(len/2+1))%4;
        if (ccc==0)
        {
            l[zz]=1000;
            r[zz]=9999;
        }
        else if (ccc==1)
        {
            l[zz]=1;
            r[zz]=9;
        }
        else if (ccc==2)
        {
            l[zz]=10;
            r[zz]=99;
        }
        else if (ccc==3)
        {
            l[zz]=100;
            r[zz]=999;
        }
    }
    else
    {
        l[zz]=1000;
        r[zz]=9999;
    }
    for (i=zz-1;i > =0;i--)
    {
        r[i]=9999;
    }
    int x;
    while (!pandeng())
    {
        erfen();
        if (pan())copy(r,b);
        else copy(l,b);
    }
    fprintf(fo,"%d",l[zz]);
    for (i=zz-1;i > =0;i--)
    {
        fprintf(fo,"%04d",l[i]);
    }
    fclose(fo);
    fclose(fp);
    return 0;
}