algorithm - 二分查找的使用

Question

我已经给出了范围 L 到 R。我必须找出 L 到 R 之间有多少个数字，这样数字的除数为奇数。

1<L<R<10^18

由于L和R相当高，所以简单的for循环会导致超时。
我发现二分搜索可以用来解决这个问题。

我不明白二分搜索如何帮助找到奇数个数的计数除数。

代码:

int find (long long n) {
    int low,high,mid;
    long long v1,v2;
    low = 1;
    high = 1e9 + 1;
    if (n == 0) {
        return 0;
    }
    while (low <= high) {
        mid = (low + high) / 2;
        v1 = mid * 1LL * mid;
        v2 = (mid + 1) * 1LL * (mid + 1);
        if (v1 <= n) {
            if (v2 > n) {
                return mid;
            } else {
                low = mid + 1;
            }
        } else {
            high = mid - 1;
        }
    }
}

和
答案:ans = find(r) - find(l - 1);请解释一下数论中二分查找的概念

Answer 1

该算法基于一个简单的事实，即为了得到奇数个除数，数字 n 必须是一个完整的正方形。否则，对于每个除数 k，还有另一个不同的除数 n/k，因此您将始终拥有偶数个除数。该算法只计算 1 和提供的 n(含)之间的完整方 block 数，这实际上是 integer square root (floor(sqrt(n)))。所以它使用二进制搜索找到平方根。如果你的平台/语言上有足够精确的 sqrt(n) 方法，你可以这样解决你的问题:

ans = floor(sqrt(r)) - floor(sqrt(l-1));

通常 double 类型不能提供足够的精度，因此结果可能少一或多一。可能这就是使用二分查找的原因。尽管如此，您仍然可以使用 sqrt。之后只需计算平方，如有必要，将结果调整一(这样会快得多)。或者，您可以使用牛顿法(调整后它比 sqrt 慢，但比二进制搜索快得多)。