比较快的开方方法是模拟手算开方，牛顿法虽然描述起来简单一些，但仔细想想，非常不合适——高精度除法消耗很多时间。
　　手算开方的过程是这样的：
1.将要开方的数字以小数点为分节，左边从右到左，右边从左到右，每两位作为一节；
2.左边第一节的数字为余数，0作为除数，商为0；
3.找到最大的小于10的试商，使(除数+试商)*试商<=余数；
4.从余数中减去(除数+试商)*试商，再从被开方数中落下两节，作为新的余数；
5.将试商写在商的后面，作为新的商；
6.将商乘以20，作为新的除数；
7.如果开方精度已经符合要求，则停止，否则返回3。
　　高精度数字用list实现，左边为高位，右边为低位。开方第3步“找到最大的小于10的试商”用二分实现。
　　Submit 1: TLE on 17。优化一些细节。
　　Submit 2: TLE on 21。看来TLE不是细节引起的。将数字的进制改成10000进制，开方第3步改成“找到最大的小于10000的试商”。
　　Submit 3: PE on 1。一个debug用的输出忘了去掉了。
　　Submit 4: AC。135ms，这个程序的高精度计算是用operator写的。
　　Submit 5: AC。67ms，改成用一般函数后，时间节约了一半。看来用operator是消耗时间的。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

#include <cstdio>
#include <list>
using namespace std;
 
typedef list<int> bignum;
 
void multi(bignum &a,int b)
{
    if (b==0)
    {
        a.clear(); a.push_back(0); return;
    }
    int t=0;
    for (bignum::reverse_iterator i=a.rbegin();i!=a.rend();i++)
    {
        *i=*i*b+t; t=*i/10000; *i%=10000;
    }
    if (t) a.push_front(t);
    return;
}
 
void add(bignum &a,int b)
{
    *a.rbegin()+=b;
    int t=0;
    for (bignum::reverse_iterator i=a.rbegin();i!=a.rend();i++)
    {
        if ((t=*i/10000)==0) break;
        *i%=10000;
    }
    if (*a.begin()>9999)
    {
        t=*a.begin()/10000; *a.begin()%=10000; a.push_front(t);
    }
}
 
void minus(bignum &a,bignum &b)
{
    int t=0;
    for(bignum::reverse_iterator i=a.rbegin(),j=b.rbegin();i!=a.rend() && j!=b.rend();i++,j++)
    {
        *i-=t;
        if ((t=*i<*j)) *i+=10000;
        *i-=*j;
    }
    *a.begin()-=t;
    while (*a.begin()==0) a.pop_front();
    return;
}
 
bool operator <(bignum &a,bignum &b)
{
    if (a.size()!=b.size()) return a.size()<b.size();
    else
    {
        pair<bignum::iterator,bignum::iterator> t=mismatch(a.begin(),a.end(),b.begin());
        return (t.first!=a.end() && *t.first<*t.second);
    }
}
 
void print(bignum &a)
{
    bignum::iterator i=a.begin();
    printf("%d",*i);
    for (i++;i!=a.end();i++)
    {
        if (*i<1000) printf("0");
        if (*i<100) printf("0");
        if (*i<10) printf("0");
        printf("%d",*i);
    }
    printf("\n");
}
 
int main()
{
    bignum square,result,div,remain;
    char buf[1001];
    scanf("%s",buf);
    for (int i=strlen(buf)-1;i>=0;i-=4)
    {
        int t=0;
        if (i>=3) t+=(buf[i-3]-48)*1000;
        if (i>=2) t+=(buf[i-2]-48)*100;
        if (i>=1) t+=(buf[i-1]-48)*10;
        t+=buf[i]-48;
        square.push_front(t);
    }
    bignum::iterator si=square.begin();
    remain.push_back(*square.begin());
    if ((square.size()&1)==0) remain.push_back(*(++si));
    div.push_back(0);
    while (si!=square.end())
    {
        bignum t,t1;
        int l=0,r=10000,m;
        result.push_back(0);
        while (r-l>1)
        {
            m=(l+r)>>1;
            t1=div; add(t1,m); multi(t1,m);
            if (!(remain<t1))
            {
                *result.rbegin()=l=m; t=t1;
            }
            else r=m;
        }
        div=result; multi(div,2); div.push_back(0);
        minus(remain,t);
        if (si!=square.end()) remain.push_back(*(++si));
        if (si!=square.end()) remain.push_back(*(++si));
    }
    print(result);
    return 0;
}