使 a*b < N 的 (a, b) 对数，其中 a、b、N 是大于 0 的整数

Question

我在 C 中有这段代码来计算此类对的数量::

long long factors(int N) {
    int nr = (int) sqrt(N);
    int b;

    int fix = N - nr * nr - 1;
    long long ans = 0;
    for (b = 2; b <= nr; b++) {
        if (N % b == 0) {
            ans += N/b - 1;
        } else {
            ans += N/b;
        }
    }

    if ( fix < 0) {
        ans = (2*ans) + N + fix;
    } else {
        ans = (2*ans) + N + fix - 1;
    }

    return ans; 
}

此函数正确计算了此类对的数量。这背后的逻辑是什么？

Answer 1

说明图

考虑以下情况的说明 N = 10，其中每个位置代表一对要计算的因素， a/N、2 和 -/* 显示计算对（如下所述）和 . 是一个占位符，用于标记在相关阶段中未计算在内的对：

  | 1   2   3   4   5   6   7   8   9
--+-~~~-===-===-----------------------
1 ! N2- a2- a2- .2. .2. .2. .2. .2. .2.
2 ! N2- a2- a2- .2.
3 ! N2- a2- a2*
4 | N.. a..
5 | N..
6 | N..
7 | N..
8 | N..
9 | N..

算法说明

该算法的有效作用是：

计算从 2 到 int (sqrt (N)) 的列（即上述情况下的 3，标记为 = 和 a ).
- 列 b 添加 N / b 除非 b 是 [=44 的因数=]N，在这种情况下，最后一个不算数。
为第一列添加 N - 1（标有 ~ 和 N）。
将其加倍，以覆盖尚未计数的行（标记为 ! 和 2）。
减去计数两次的区域（标记为-），其大小为nr²，如果nr² = N，因为在那种情况下我们不会计算 (nr,nr) (标有 * 而不是 -).

如果去掉fix的计算和测试，fix的计算和代码的最后部分（and）可能会重新排列如下：

    ans = ans + N - 1;              // Add in the first column
    ans = 2 * ans;                  // Double to cover rows as well

    if ( nr * nr != N )             // Equivalent to fix >= 0
        ans = ans -  nr * nr;       // Subtract the square region counted twice
    else
        ans = ans - (nr * nr - 1);  // We did not count (nr,nr)

注释代码

发布的代码，经过轻微改编（假设为 C99/MSVS 2012+）并评论：

long long factors(int N) {
    long long ans = 0;        // Result to return
    int nr = (int) sqrt(N);   // Highest possible value of the lower factor

    // Count factorisations (a,b) with a ∈ 2..√N
    for (int b = 2; b <= nr; b++) {
        if (N % b == 0) {    // If b | N ..
            ans += N/b - 1;  // .. then b*(N/b) = N, so count 1..(N/b - 1)
        } else {
            ans += N/b;      // .. count 1..N/b
        }
    }

    // Remaing steps of algorithm, optimised:
    // - Add N-1 for 1st column (1,1..(N-1)), giving total (a,b) with a ∈ 1..√N
    // - Double, to cover the reversed pairs (b,a) with a ∈ 1..√N, b ∈ √N..N
    // - Subtract nr² or nr²-1, for pairs counted twice
    int fix = N - nr * nr - 1;     // A correcting term, chosen to compare to 0
    if ( fix < 0) {                   // I.e. if nr² = N ..
        ans = (2*ans) + N + fix;      // .. ans = 2*(ans + N-1) - (nr² - 1)
    } else {
        ans = (2*ans) + N + fix - 1;  // .. ans = 2*(ans + N-1) - (nr²)
    }

    return ans; 
}

Answer 2

它发生的方式是：

计算平方根。因此，如果平方根不是（比如说）并且 N 不是平方数，那么可以自身相乘且小于 N 的最大允许数不是。
我们通过修复 variable.If 数字是否为正方形来检查数字是否为正方形，然后一种可能性较小，即 no*no=N 不可能是 case.So 我们如代码所示减去 1：

其他{
ans = (2*ans) + N + fix - 1; }
接下来我们运行从 2 到平方根的循环找到可以与每个循环元素相乘且仍然小于 N 的最大元素数。

例如，让 N 为 15 对于 b=2 可以有 N/2= 7 个元素可以乘以 2 并且小于 15
2X1,2X2.........2X6,2X7 我们添加 7 个答案到 ans .对于 b=3 N/3=5 所以可以有 N/3-1 个元素，因为 3*5=15 这是不允许的。 3X1,3*2....3X4 我们给 ans 添加 4 个答案以此类推编号
现在每对 (a,b) 都会有一对 (b,a) 所以我们将 ans 乘以 2。
到目前为止，我们已经考虑了 N/2 的 a 和 b，因为我们使用了 2.In 的循环，这种情况（N=15）最大 a 或 b 是 7显示。（2X7）。还存在 N/2 个值，当乘以 1 时小于 N.In 这个（N=15）情况，即 8,9,10,11,12,13,14。所以会有 2*(N/2) 。即，要添加到 ans 的 N 个案例。所以ans加了N.
最后我们添加了修复程序来处理非正方形的额外情况。

使 a*b < N 的 (a, b) 对数，其中 a、b、N 是大于 0 的整数

Number of pairs (a, b) such that a*b < N where a, b, N are integers greater than 0

c

math

counting

说明图

算法说明

注释代码