问题标题: 求整数的平方根

Question

1

已解决

孙志浩

资深守护

求整数的平方根，至少100位。用高精度，二分。

孙志浩在2019-03-21 20:13:45追加了内容

long double只有15位！我要高精度，100位，时空要求10s/1MB。

我NOIP考250，就这点知识吗？

酷町豆刷题求解 C++ 1条评论 5 年，1 月前

Answer 1

已采纳

赵逸凡

初级启示者

(建议问黄柏墉）

牛顿迭代法的话建议通过二分，三分或者是枚举10的n次方是否>x，平方根竖式如果加上剪枝枚举时可以优化时间，但代码实现还没学到数论所以认为可以把x平方根的结果看成a*a，二分a的值，或者使用快速幂，把a的值尽量看成b*b的值左右,然后把b看成c*c.....最后把能被sqrt函数取值的z通过向上/下枚举反复接近正确答案。

赵逸凡在2019-11-07 12:41:46追加了内容

@孙志浩我只能先给你主程序的部分代码，函数体还没写好

memset(target.num,0,sizeof(target.num));
    target.len=s.length();
    for(i=1;i<=target.len;i++)
        target.num[i]=s[target.len-i]-     '0'   ;
    memset(left.num,0,sizeof(left.num));
    left.len=1;
    left.num[1]=1;
    right=target;
    do{
        middle=average(left,right);
        if(over(      times(middle,middle),target        ))
            right=middle;
        else
            left=middle;
    }while(!over(plustwo(left),right) );

注：main函数的部分代码

Answer 2

李明翰

新手光能

sqrt，大家都知道，可惜他不采纳

Answer 3

屈子元

初级守护

sqrt不支持高精度，得先定义一个高精度乘法函数，然后二分找解，二分的时间复杂度仅为logn，即使高精度乘法是n^2的也不会超时

Answer 4

邓涵睿

中级天翼

sqrt

Answer 5

潘孝宇

初级光能

everybody!

他说的是高精度，哪里能用sqrt!

Answer 6

褚俊皓

新手天翼

sqrt

前面加 cmath头文件

Answer 7

毛润宇

新手天翼

sqrt

前面加 cmath头文件

Answer 8

毛润宇

新手天翼

sqrt

前面加 cmath头文件

Answer 9

李泽远

高级天翼

可以使用sqrt()函数，里面接受1个参数，要用math.h头文件。

Answer 10

郑金顺

中级光能

sprt

Answer 11

吕牧原

高级守护

sqrt不支持高精度

Answer 12

吕牧原

高级守护

可以用sqrt函数哦

Answer 13

王鑫烨

中级光能

高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！高精度！

Answer 14

詹子都

新手光能

sqrt

Answer 15

李逸凡

新手守护

直接用sqrt函数，再加上头文件。但sqrt不是高精度，不一定能对。

Answer 16

包涵宇

中级天翼

sqrt,加头文件<cmath>或<math.h>

Answer 17

姜思远

初级光能

sqrt

前面加 cmath头文件

Answer 18

王昊宇

新手守护

#include<bits/stdc++.h>

Answer 19

黄钰杰

初级守护

可以用sqrt函数哦：sqrt(一个变量)

100位可以用数组

你很有钱啊，一个问题120酷町豆

Answer 20

吴君昊

新手光能

sqrt,或i*i<=n在循环条件里

Answer 21

王子健

初级天翼

用sqrt函数

Answer 22

王子健

初级天翼

用sqrt函数

Answer 23

被禁言

李秉轩

修练者

可以用sprt()函数要加<cmath>头文件

Answer 24

被禁言

李秉轩

修练者

可以用sprt()函数要加<cmath>头文件

Answer 25

程天瑞

资深守护

简单，sqrt

Answer 26

高杨

资深守护

可以用sqrt函数哦：sqrt(一个变量)

高杨在2019-03-23 11:01:16追加了内容

100位可以用数组

高杨在2019-03-23 11:02:40追加了内容

你很有钱啊，一个问题120酷町豆

Answer 27

欧阳语聪

资深守护

sprt

Answer 28

欧阳语聪

资深守护

sprt

Answer 29

潘晨皓

高级天翼

sqrt

Answer 30

黄子阳

资深守护

sqrt,加头文件<cmath>或<math.h>

Answer 31

董宇昊

初级启示者

sprt函数

Answer 32

吴文光

新手光能

sqrt

Answer 33

贾志骜

新手光能

sqrt

Answer 34

徐紫尘

高级光能

sqrt,加头文件<cmath>或<math.h>

Answer 35

何羽凡

修练者

可以用sqrt函数来做。

望采纳！！！

问题标题: 求整数的平方根

35 个回答: