题目大意：给出一个正整数n，求n开根号后的整数部分的值。n的位数不超过1000位。（本文不仅介绍2种解法，还会教你如何手算开根！）

输入描述 Input Description

读入一个不超过1000位的正整数n。

输出描述 Output Description

输出所求答案

样例输入 Sample Input

17

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

n为不超过1000位的正整数 满足 1<=n <10^1000

解题思路

1、二分答案：结果约500位，二分答案只需要不到1670次，每次只需计算答案的平方（复杂度500^2），再与原数据进行比较。

2、模拟开方，复杂度O(n^2)。首先要会手算开方，不然如何模拟？

程序实现

手算开根

上图中，364是怎么来的？(9*20+2) * 2 = 437。

因为(x+y)² = x² + 2xy + y² = x² + y * (2x+y)，所以92² = (90+2)² = 90² + 2 * (2*90+2) = 90² + (9*20+2) * 2，因为90²已经加过了，所以不需要再加。

同样地，7376 = ( 92  * 20 +  4  ) *  4  。