主题：郁闷呀……
Lovely哆啦
[专家分：1360] 发布于 2007-09-30 21:16:00
题目：给定一个正整数X(1<=x<=10^1000),求最大的整数N使N^2<=X
Sample Input
16
Sample Output
4
回复列表 （共7个回复）
沙发
Matodied [专家分：7560] 发布于 2007-10-01 11:15:00
超级简单的高精度乘法。
郁闷什么？？
板凳
Lovely哆啦 [专家分：1360] 发布于 2007-10-01 13:49:00
这可不是什么超级简单的高精度乘法，这是高精度开平方！
3 楼
Lovely哆啦 [专家分：1360] 发布于 2007-10-01 14:18:00
太郁闷了！怎么没人帮帮我呀？
moz你们都去哪了？
4 楼
Matodied [专家分：7560] 发布于 2007-10-02 20:43:00
开平方的公式是这个：
X(n + 1) = a IF n = 0
X(n + 1) = (Xn + a / Xn) / 2 IF n > 0
直到ABS(Xn - X(n - 1)) < T为止（假设T = 0.000001）
也就是说，只要用到带小数的高精度加法和除法就行了。
也可以从1开始循环，每循环一个数就做一次高精度乘法N*N，但这样效率低。
第3种方法：N ^ 2 = 1 + 3 + 5 + ... + N * 2 - 1
所以可以一直把X做高精度减法，第一次减1、第2次减3...直到X<0，再把减的次数减1就是N。
5 楼
moz [专家分：37620] 发布于 2007-10-03 01:20:00
[quote]发表时间：2007-10-1 14:18:00 [回复] [引用]
3 楼
太郁闷了！怎么没人帮帮我呀？
moz你们都去哪了？[/quote]
这个时候我在举行婚礼.谢谢.
6 楼
Matodied [专家分：7560] 发布于 2007-10-03 10:26:00
moz 不要把和题目无关的事带到这里来。
还有你说我的第3种方法怎么样？高精度乘法都省了。
7 楼
Lovely哆啦 [专家分：1360] 发布于 2007-10-03 19:25:00
太感谢了!
我来回复
您所在位置：