【欧拉计划第 12 题】 高度可除的三角数 Highly divisible triangular number

发表于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

Problem 12 Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$. The first ten terms would be:

$$
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
$$

Let us list the factors of the first seven triangle numbers:

We can see that $28$ is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

问题 12 高度可除的三角数

三角数由依次排列的自然数的和生成。所以第 $7$ 个三角数是 $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$。前十项是：

$$
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
$$

让我们列出前七个三角数的因数：

我们可以看到 $28$ 是第一个有五个以上除数（因子）的三角数。
第一个有超过 $500$ 个除数（因子）的三角数的值是多少？

思路分析

拿到题目，我们首先做的要理解清除题目含义，对于从未听过的陌生概念、术语（一般会举例说明），我们也要试着首先理解示例

这里解释下题目中的三角数是如何得出的，请看下表计算过程

第 x 个 三角数值 计算过程
1 1 1
2 3 1+2=3
3 6 1+2+3=6
4 10 1+2+3+4=10
5 15 1+2+3+4+5=15
6 21 1+2+3+4+5+6=21
7 28 1+2+3+4+5+6+7=28
… … …

依然是老朋友，暴力枚举，从 $1$ 开始依次枚举每个数字并判断它有多少个约数

当约数个数大于 $500$ 时，退出循环并输出该值

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
 * @Author: coder-jason
 * @Date: 2022-04-19 20:58:43
 * @LastEditTime: 2022-04-19 21:58:30
 */
#include <bits/stdc++.h>
using namespace std;

int factor(long long n) // 计算数字 num 因数个数 , 注意数据范围
{                     
    int count = 0;
    for (long long i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            if (i * i == n)
                count++;
            else
                count += 2;
        }
    }
    return count;
}

int main()
{
    int num = 0;
    for (long long i = 1;; i++)
    {
        num += i;              // 枚举三角数 循环过程可参照末尾注解
        if (factor(num) > 500) // 传值给 facto() 返回 num 因数个数
        {
            cout << num << endl; // 满足条件"第一个有超过 500 个因子"的三角数时,输出 num 值
            break;               // 循环结束
        }
    }
    return 0;
} // num i num+=i; 过程演示
  // 0 1
  // 1 2
  // 3 3
  // 6 4
  // 10 5

答案：76576500

本题在完成三角数的枚举后，最重要的一步是如何判断一个数约数的个数

从基本思想不断优化，降低算法的时间复杂度，详请参考快速计算约数的个数——从基础到高级