当前位置:首页 > 高精度 > 正文
CodeVS3119高精度练习之大整数开根
4615+

题目大意:给出一个正整数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)2 = x2 + 2xy + y2 = x2 + y * (2x+y),所以922 = (90+2)2 = 902 + 2 * (2*90+2) = 902 + (9*20+2) * 2,因为902已经加过了,所以不需要再加。

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

About

坚决不Copy代码!

本文标签:,,

CodeVS3119高精度练习之大整数开根:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!