c - 如何找到从 1 到 n 和从 n+1 到 m 的和相同的数对

Question

所以，我必须为大学做一个工作，它包括创建一个算法。

该算法必须找到满足特定条件的数对，即:从 1 到 n(不包含)的总和结果与从 n+1 到 m(含)。

在最后，算法必须给出至少 15 对。

第一对是6和8，因为从1到n(不包括)(6)是 1+2+3+4+5 = 15 并且从 n+1 到 m 是 8+7 = 15。

我创建的算法如下:

int main() {
    int count = 0;
    unsigned int before = 0;
    unsigned int after = 0;
    unsigned int n = 1;
    unsigned int m = 0;
    do {
        before += n - 1;
        after = n + 1;
        for (m = after + 1; after < before; m++) {
            after += m;
        }
        if (before == after) {
            printf("%d\t%d\n", n, (m - 1));
            count++;
        }
        n++;
    } while (count < 15);
}

这实际上是可以的，但是有些输出不正确，而且在复杂性方面也很糟糕，而且由于我正在研究算法的复杂性，所以最好找到一些比这个更好的算法。

我也试过用 Java 来做，但是使用 int 对这个问题不好，而使用 long，计算需要数小时和数小时。

到目前为止我找到的数字:

6 and 8  
35 and 49  
204 and 288   
1189 and 1681  
6930 and 9800  
40391 and 57121  

以下可能是错误的:

100469 and 107694  
115619 and 134705  
121501 and 144689  
740802 and 745928  
1250970 and 1251592  
2096128 and 2097152  
2100223 and 2101246  
4196352 and 8388608  
18912301 and 18912497  

Answer 1

除了前 6 个之外，您的结果不正确:unsigned int 类型的范围不足以存储总和。您应该为 before 和 after 使用 unsigned long long 类型。

此外，对于大值，您的算法变得非常慢，因为您从头开始为 before 的每个新值重新计算 after，时间复杂度为 O( N²)。您可以并行保持 2 个运行和并将复杂度降低到准线性。

最后但同样重要的是，UINT32_MAX以下只有 12 种解决方案，因此类型 unsigned long long，保证至少有 64 个值位 n 和 m 也是如此。为避免不正确的结果，在更新 after 时应测试溢出。

进一步的测试表明，对于 8589934591 附近的 m 值，after 和 before 的总和超过 64 位。一个解决方案是当 before 和 after 达到 2⁶³ 时都减去 2⁶²。通过此修改，程序可以继续搜索更大的 n 和 m 值，远远超过 32 位。

这是一个改进的版本:

#include <stdio.h>

int main() {
    int count = 0;
    unsigned long long n = 1;
    unsigned long long m = 2;
    unsigned long long before = 0;
    unsigned long long after = 2;

    for (;;) {
        if (before < after) {
            before += n;
            n++;
            after -= n;
        } else {
            m++;
            /* reduce values to prevent overflow */
            if (after > 0x8000000000000000) {
                after -= 0x4000000000000000;
                before -= 0x4000000000000000;
            }
            after += m;
            while (before > after) {
                after += n;
                n--;
                before -= n;
            }
        }
        if (before == after) {
            printf("%llu\t%llu\n", n, m);
            count++;
            if (count == 15)
                break;
        }
    }
    printf("%d solutions up to %llu\n", count, m);
    return 0;
}

输出(运行时间 30 分钟):

6       8
35      49
204     288
1189    1681
6930    9800
40391   57121
235416  332928
1372105 1940449
7997214 11309768
46611179        65918161
271669860       384199200
1583407981      2239277041
9228778026      13051463048
53789260175     76069501249
313506783024    443365544448
15 solutions up to 443365544448