如何修复寻找含k个因数的最小三角数代码的测试用例超时问题？

你的代码逻辑是对的，但确实存在两个核心低效点：一是因数计数的循环范围太大，二是没有利用三角数的数学性质来减少重复计算。下面一步步拆解优化方案：

1. 先优化因数计数的核心逻辑 #

原代码里for (int i = 1; i <= sum / 2; i++)的循环范围完全没必要——因数是成对存在的：如果i是sum的因数，那么sum/i也一定是它的因数。我们只需要循环到sqrt(sum)就可以完成计数，循环次数直接从O(sum)降到O(√sum)，速度提升非常明显。

修改后的因数计数函数：

int count_divisors(long long num) {
    if (num == 0) return 0;
    int count = 0;
    long long sqrt_num = sqrt(num);
    for (long long i = 1; i <= sqrt_num; i++) {
        if (num % i == 0) {
            // 若i和num/i相等，只算一次；否则算两个因数
            count += (i == num / i) ? 1 : 2;
        }
    }
    return count;
}

注意这里用了long long类型，因为三角数增长很快，大n对应的sum会超出32位int的范围，避免溢出。

2. 利用三角数的互质性质减少计算量 #

三角数的公式是T(n) = n(n+1)/2，而相邻整数n和n+1必然互质（最大公约数为1）。根据数论性质：如果a和b互质，那么ab的因数个数等于a的因数个数乘以b的因数个数。

我们可以分两种情况处理：

• 当n是偶数时：n=2m，则T(n)=m*(2m+1)，m和2m+1互质，因数个数= d(m)*d(2m+1)
• 当n是奇数时：n+1=2m，则T(n)=n*m，n和m互质，因数个数= d(n)*d(m)

基于这个性质，我们不需要每次都计算整个T(n)的因数个数，只需要维护n和n+1的因数个数，每次递增n时更新其中一个即可，进一步减少重复计算：

#include <stdio.h>
#include <math.h>

int count_divisors(long long num) {
    if (num == 0) return 0;
    int count = 0;
    long long sqrt_num = sqrt(num);
    for (long long i = 1; i <= sqrt_num; i++) {
        if (num % i == 0) {
            count += (i == num / i) ? 1 : 2;
        }
    }
    return count;
}

int main() {
    int k;
    scanf("%d", &k);
    if (k == 1) { // 特殊情况：第一个三角数1只有1个因数
        printf("1");
        return 0;
    }

    long long n = 1;
    int d_n = count_divisors(n);
    int d_n1 = count_divisors(n+1);

    while (1) {
        int divisors;
        if (n % 2 == 0) {
            divisors = count_divisors(n/2) * d_n1;
        } else {
            divisors = d_n * count_divisors((n+1)/2);
        }

        if (divisors == k) {
            printf("%lld", n*(n+1)/2);
            break;
        }

        // 更新n和n+1的因数计数，为下一次循环做准备
        n++;
        d_n = d_n1;
        d_n1 = count_divisors(n+1);
    }
    return 0;
}

3. 可选进阶优化：质因数分解法计算因数个数 #

如果k很大（比如k=100），可以用质因数分解进一步提升因数计数的速度：先把数字分解为p1^a1 * p2^a2 * ... * pn^an，那么因数个数就是(a1+1)*(a2+1)*...*(an+1)。这个方法对于大数的因数计数效率比遍历到√num更高。

示例质因数分解实现：

int count_divisors_via_factorization(long long num) {
    if (num == 1) return 1;
    int count = 1;
    // 分解2的幂次
    int exponent = 0;
    while (num % 2 == 0) {
        exponent++;
        num /= 2;
    }
    if (exponent > 0) count *= (exponent + 1);
    // 分解奇数因子
    for (long long i = 3; i*i <= num; i += 2) {
        exponent = 0;
        while (num % i == 0) {
            exponent++;
            num /= i;
        }
        if (exponent > 0) count *= (exponent + 1);
    }
    // 如果剩余的num是质数
    if (num > 1) count *= 2;
    return count;
}

把这个函数替换之前的count_divisors，对于大数字的处理速度会再上一个台阶。

内容的提问来源于stack exchange，提问作者marmofayezi