(大整数开方) 输入一个正整数n（1≤n≤10

(大整数开方) 输入一个正整数n（1≤n≤10¹⁰⁰），试用二分法计算它的平方根的整数部分。

#include

#include

using namespace std;

const int SIZE=200;

struct hugeint{

\tint len,num[SIZE];

};

//其中 len 表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推

hugeint times(hugeint a,hugeint b)

// 计算大整数 a 和 b 的乘积

{

\tint i,j;

\thugeint ans;

\tmemset(ans.num,0,sizeof(ans.num));

\tfor(i=1;i<=a.len;i )

\t\tfor(j=1;j<=b.len;j )

\t\t ① =a.num[i]*b.num[j];

\t for(i=1;i<=a.len b.len;i ){

\t\t ans.num[i 1] =ans.num[i]/10;

\t ② ;

\t}

\tif(ans.num[a.len b.len]>0)

\t\tans.len=a.len b.len;

\telse

\t\tans.len=a.len b.len-1;

\treturn ans;

}

hugeint add(hugeint a,hugeint b)

//计算大整数 a 和 b 的和

{

\tint i;

\thugeint ans;

\tmemset(ans.num,0,sizeof(ans.num));

\tif(a.len>b.len)

\t\tans.len=a.len;

\telse

\t\tans.len=b.len;

\tfor(i=1;i<=ans.len;i ){

\t\tans.num[i] = ③ ;

\t\tans.num[i 1] = ans.num[i]/10;

\t\tans.num[i]%=10;

\t}

\tif(ans.num[ans.len 1]>0)

\t\tans.len ;

\treturn ans;

}

hugeint average(hugeint a,hugeint b)

//计算大整数 a 和 b 的平均数的整数部分

{

\tint i;

\thugeint ans;

\tans=add(a,b);

\tfor(i=ans.len;i>=2;i--){

\t\tans.num[i-1] =( ④ )*10;

\t\tans.num[i]/=2;

\t}

\tans.num[1]/=2;

\tif(ans.num[ans.len]==0)

\t\tans.len--;

\treturn ans;

}

hugeint plustwo(hugeint a)

// 计算大整数 a 加 2 之后的结果

{

\tint i;

\thugeint ans;

\tans=a;

\tans.num[1] =2;

\ti=1;

\twhile( (i<=ans.len)&&(ans.num[i]>=10) ){

\t\tans.num[i 1] =ans.num[i]/10;

\t\tans.num[i]%=10;

\t\ti ;

\t}

\tif(ans.num[ans.len 1]>0)

\t ⑤ ;

\treturn ans;

}

bool over(hugeint a,hugeint b)

// 若大整数 a>b 则返回 true，否则返回 false

{

\tint i;

\tif( ⑥ )

\t\treturn false;

\tif( a.len>b.len )

\t\treturn true;

\tfor(i=a.len;i>=1;i--){

\t\tif(a.num[i]

\t\t\treturn false;

\t\tif(a.num[i]>b.num[i])

\t\t\treturn true;

\t}

\treturn false;

}

int main()

{

\tstring s;

\tint i;

\thugeint target,left,middle,right;

\tcin>>s;

\tmemset(target.num,0,sizeof(target.num));

\ttarget.len=s.length();

\tfor(i=1;i<=target.len;i )

\t\ttarget.num[i]=s[target.len-i]- ⑦ ;

\tmemset(left.num,0,sizeof(left.num));

\tleft.len=1;

\tleft.num[1]=1;

\tright=target;

\tdo{

\t\tmiddle=average(left,right);

\t\tif(over( ⑧ ))

\t\t\tright=middle;

\t\telse

\t\t\tleft=middle;

\t}while(!over(plustwo(left),right) );

\tfor(i=left.len;i>=1;i--)

\t\tcout<

\treturn 0;

}