(大整数开方) 输入一个正整数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(hugeinta,hugeintb)

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

{

\tinti,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 )

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

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

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

② ;

\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(hugeinta,hugeintb)

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

{

\tinti;

\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(hugeinta,hugeintb)

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

{

\tinti;

\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(hugeinta)

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

{

\tinti;

\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)

⑤ ;

\treturn ans;

}

boolover(hugeinta,hugeintb)

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

{

\tinti;

\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;

\tinti;

\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;

}