c - 计算C中极大数的平方根

This question already has answers here:

How is the square root function implemented?
                                
                                    （12个答案）
                                
                        
                                2年前关闭。
            
                    
我正在解决奥林匹克竞赛中的一些任务，但我陷入了一个问题。我找到了该任务的解决方案，但是我的解决方案需要平方根。我的代码对于前12个输入正常工作，但随后给出了错误的答案。我猜这是由于输入量极大，可能高达10 ^ 400000。所以我想知道是否有办法计算C中这些极大输入的平方根的整数部分。这是代码：

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int main(){
    long long n;
    scanf("%lld", &n);
    long long ans;
    ans = sqrtl(n-1);
    long long result;
    result = ans+1-llabs(n-ans*ans-(ans+1));
    printf("%lld\n", result);
    return 0;
}

最佳答案

简而言之，您可以使用二分法滚动长平方根算法，如下所示：


选择一个长数字表示形式（无符号整数数组）；
进行长的加减运算（除进位以外，相当琐碎）；
实施减半（也需要对进位进行一些照顾）；
实现长时间比较（类似于减法）。


[请注意，加法使您可以实现加倍和四倍，而减半还可以除以四。

然后设置d= 1，并反复将d翻倍直到d² > N。 （每次将d翻倍，就会将d²翻四倍。）

接下来，设置a= 0以便不变量

a² ≤ N < (a + d)²

被建立，并在保持不变的情况下反复将d减半。这是通过实现

d= d/2;如果N < (a + d)²，则设置a= a + d;否则保持a不变。

最后，您将缩小到

a² ≤ N < (a + 1)²

因此a是整数平方根。

评估条件

N < (a + d)² = a² + 2ad + d²,

要么

N - a² < 2ad + d²,

只需跟踪N - a²，2ad和d²术语，并在修改d或a时对其进行更新即可。这仅需要上述原始操作。

关于c - 计算C中极大数的平方根，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48176305/