欧拉计划 12

Highly divisible triangular number

题目描述

三角形数的第 项定义为 到 的所有数之和：
是第一个拥有 个因子（）的三角形数
求第 个拥有 个因子的三角形数

思路1

写出通项
因为 和 是互质的，所以想到了递归的思路

记 为 的因子个数，则可以得到下面的公式

但是在写代码的时候发现，这种解法存在两个问题

1. 只有第一次计算时能轻松将参数拆解成两个互质的数的乘积，后面的拆解并不容易
2. 前后两项之间的状态转移并不平滑，不好做 优化，需要开很大的 数组

所以这种解法只能算是一个思路（理论上每个数都可以拆解成两个互质的数的乘积），解题并不适合

思路2

遍历三角形数，计算每一项的因子个数

计算一个数 的因子个数有两种方法：
一种是遍历因子法，遍历 ，判断是否为较小的因子即可
另一种是遍历素因子法，计算每个素因子个数，通过组合得到答案

方法一的时间复杂度固定为 ，方法二的时间复杂度为 ， 为 的最大素因子
在实际测试中发现方法二的效率约为方法一的一倍
这似乎有点反常，试想一下如果 是一个素数，那么方法二就是 级的算法
然而实际情况是，素数覆盖率并没有那么大，很多数的最大素因子比自身平方根还要小

代码

// 三角形数的第 n 项定义为 1 到 n 的所有数之和：1, 3, 6, 10, 15, 21, 28
// 28 是第 1 个拥有 5 个因子的三角形数，求第 1 个拥有 500 个因子的三角形数
#include <cstdio>

// 计算 x 有多少因子
int calc1(int x) {
    int ans = 0;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            if (i * i == x) ans++;
            else ans += 2;
        }
    }
    return ans;
}

int calc2(int x) {
    int ans = 1;
    for (int d = 2; x > 1; d++) {
        int cnt = 1;
        while (x % d == 0) x /= d, cnt++;
        ans *= cnt;
    }
    return ans;
}

int main() {
    for (int i = 1, x = 1; ; i++, x += i) {
        if (calc2(x) > 500) {
            printf("%d\n", x);
            break;
        }
    }
    return 0;
}