题目12：第一个拥有超过500个约数的三角形数是多少？

欧拉计划

题目12：第一个拥有超过500个约数的三角形数是多少？

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:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

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?

题目翻译：

三角形数序列是由对自然数的连加构造而成的。

所以第七个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。

那么三角形数序列中的前十个是：

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

下面我们列出前七个三角形数的约数：

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

可以看出 28 是第一个拥有超过 5 个约数的三角形数。

那么第一个拥有超过 500 个约数的三角形数是多少？


视频讲解：




思路解析及源码参考（C & Python）：

游客，如果您要查看本帖隐藏内容请回复

zhangjinxuan

这是我的代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int MAXN = 100000;
   
5. int tot[MAXN + 1];
   
6. int pms[MAXN + 1], pmtot;
   
7. bool nopm[MAXN + 1];
   
8. 
   
9. void get_prime() { //为了优化极致，使用质数筛
   
10.         nopm[1] = 1;
    
11.         for (int i = 2; i <= MAXN; ++i) {
    
12.                 if (!nopm[i]) pms[++pmtot] = i;
    
13.                 for (int j = 1; j <= pmtot && 1ll * pms[j] * i <= MAXN; ++j) {
    
14.                         nopm[pms[j] * i] = 1;
    
15.                         if (i % pms[j] == 0) {
    
16.                                 break;
    
17.                         }
    
18.                 }
    
19.         }
    
20. }
    
21. 
    
22. int solve(long long number) { // 分解质因数而求因子数
    
23.         int ans = 1;
    
24.         int yn = number;
    
25.         for (int j = 1; j <= pmtot && 1ll * pms[j] * pms[j] <= number; ++j) {
    
26.                 int tmp = 1;
    
27.                 while (number % pms[j] == 0) {
    
28.                         ++tmp;
    
29.                         number /= pms[j];
    
30.                 }
    
31.                 ans *= tmp;
    
32.                 // 因子个数 = Π(ei + 1)
    
33.         }
    
34.         if (number > 1) ans *= 2;
    
35.         return ans;
    
36. }
    
37. 
    
38. int main() {
    
39.         // a * (a - 1) / 2
    
40.         get_prime();
    
41.         for (int i = 1; i <= MAXN; ++i) { // 枚举 a
    
42.                 // 此时将 (i - 1) 与 i 相乘除以 2 即可。
    
43.                 int tmp = solve(1ll * i * (i - 1) / 2); // (i - 1) * i / 2 的因子总数
    
44.                 if (tmp >= 500) {
    
45.                         printf("%lld\n", 1ll * i * (i - 1) / 2);
    
46.                         return 0;
    
47.                 }
    
48.         }
    
49.         return 0;
    
50. }

复制代码

主要思路：

因为“三角形数”一定可以表示成 a * (a - 1) / 2 的形式，那么我们就枚举 a，然后求出 a * (a - 1) / 2 的因子个数即可。

当然，我这个代码有一些多余的 solve 调用，时间复杂度 O(MAXN ** 2))， 不知道算对没有，我用了质数筛优化的，但跑得很快。

zhangjinxuan

我这个蒟蒻的算法居然和版主的算法差不多

欧拉计划

zhangjinxuan 发表于 2023-7-4 19:16
我这个蒟蒻的算法居然和版主的算法差不多

鱼C-小师妹

pixie99

有你精彩，努力更新

1449620085

siazb8590

我来学习啦

auend

这个有意思 。

Mr.roushan

看看

nkysp

好

sharp46

hejiage

今天又多学习了一个

kittennnn

kalendd

太难了，还用到了数学里的定理

dou820

太难了，还用到了数学里的定理