UVA数论中有道题是求10^1000以内的数的开方（数据中每个数保证是某个正整数的平方）
手算开平方，是我认为最有效的方法。但是我不是很懂... ...
请各位大牛来解释，最后来个伪代码

为何空无一人？？

求顶起！

求平方根的算法，可以利用牛顿法来解方程x^2 - n = 0
有递归式：
x_k+1 = (x_k + n / x_k) / 2
初始x0可以选择n

PS：教你cheat对于uva的这题，用long double类型就能AC

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1000+10;

struct bign
{
      int len,s[maxn];
      bign() { len=1; memset(s,0,sizeof(s)); }
};
bign n;
int test,all;

bign init()
{
     bign c;
     char s[maxn]; scanf("%s",s);
     c.len=strlen(s);
     for (int i=1;i<=c.len;i++)
         c.s[i]=s[c.len-i]-'0';
     return c;
}

bign past(bign a,int b)
{
     a.s[1]+=b;
     for (int i=1;a.s[i]>=10;i++)
     {
         a.s[i+1]+=a.s[i]/10;
         a.s[i]%=10;
     }
     while (a.s[a.len+1]>0)
           a.len++;
     return a;
}

bign time(bign a,int b)
{
     for (int i=1;i<=a.len;i++)
     {
         a.s[i]*=b;
         if (i>1)
         {
            a.s[i]+=a.s[i-1]/10;
            a.s[i-1]%=10;
         }
     }
     while (a.s[a.len]>=10)
     {
           a.s[a.len+1]+=a.s[a.len]/10;
           a.s[a.len]%=10;
           a.len++;
     }
     return a;
}

bool more(bign a,bign b)
{
     if (a.len>b.len) return true;
     if (a.len<b.len) return false;
     for (int i=a.len;i>=1;i--)
     {
         if (a.s[i]>b.s[i]) return true;
         if (a.s[i]<b.s[i]) return false;
     }
     return true;
}

bign cut(bign a,bign b)
{
     for (int i=1;i<=a.len;i++)
     {
         a.s[i]-=b.s[i];
         if (a.s[i]<0)
         {
            a.s[i]+=10;
            a.s[i+1]--;
         }
     }
     while (a.s[a.len]==0 && a.len>1)
           a.len--;
           
     return a;
}

void ouit(bign a)
{
     for (int i=a.len;i>=1;i--)
         printf("%d",a.s[i]);
     printf("\n");
}

int main()
{
    scanf("%d",&test); all=test;
    while (test--)
    {
          if (test<all-1) printf("\n");
          n=init();
          bign ans,remain;
         
          for (int i=(n.len+1)/2*2;i>=2;i=i-2)
          {
              int group = n.s[i]*10 + n.s[i-1];
              
              bign odd;
              odd=time(ans,20);
              odd=past(odd,1);

              remain=time(remain,100);
              remain=past(remain,group);
   
              int count=0;
              while (more(remain,odd))
              {
                    count++;
                    remain=cut(remain,odd);
                    odd=past(odd,2);
              }
         
              ans=time(ans,10);
              ans=past(ans,count);
          }
         
          ouit(ans);
    }
    return 0;
}

...

用 泰勒公式 展开 求根 式！忽略 高阶 数。

long double能表示到10的500次方么？我真不知道。
要我还是得做大数运算，不过用牛顿迭代法需要做大数除法，所以我会选择试商，这样只需要做大数乘法就可以了。
算法复杂度应该是log(log(n))

废话，本来就是试商。。。。