欧拉计划 发表于 2023-7-3 23:27:12

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

本帖最后由 欧拉计划 于 2023-8-5 23:09 编辑

题目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 that28is 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 个约数的三角形数是多少？


视频讲解：

https://www.bilibili.com/video/BV1c14y1d7Rw/


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

**** Hidden Message *****

zhangjinxuan 发表于 2023-7-4 11:18:30

这是我的代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
int tot;
int pms, pmtot;
bool nopm;

void get_prime() { //为了优化极致，使用质数筛
        nopm = 1;
        for (int i = 2; i <= MAXN; ++i) {
                if (!nopm) pms[++pmtot] = i;
                for (int j = 1; j <= pmtot && 1ll * pms * i <= MAXN; ++j) {
                        nopm * i] = 1;
                        if (i % pms == 0) {
                                break;
                        }
                }
        }
}

int solve(long long number) { // 分解质因数而求因子数
        int ans = 1;
        int yn = number;
        for (int j = 1; j <= pmtot && 1ll * pms * pms <= number; ++j) {
                int tmp = 1;
                while (number % pms == 0) {
                        ++tmp;
                        number /= pms;
                }
                ans *= tmp;
                // 因子个数 = Π(ei + 1)
        }
        if (number > 1) ans *= 2;
        return ans;
}

int main() {
        // a * (a - 1) / 2
        get_prime();
        for (int i = 1; i <= MAXN; ++i) { // 枚举 a
                // 此时将 (i - 1) 与 i 相乘除以 2 即可。
                int tmp = solve(1ll * i * (i - 1) / 2); // (i - 1) * i / 2 的因子总数
                if (tmp >= 500) {
                        printf("%lld\n", 1ll * i * (i - 1) / 2);
                        return 0;
                }
        }
        return 0;
}

主要思路：

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

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

zhangjinxuan 发表于 2023-7-4 19:16:02

我这个蒟蒻的算法居然和版主的算法差不多{:10_257:}

欧拉计划 发表于 2023-7-4 19:20:35

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

{:10_282:}

鱼C-小师妹 发表于 2023-7-5 14:37:34

{:9_227:}

pixie99 发表于 2023-7-12 09:22:23

有你精彩，努力更新

1449620085 发表于 2023-7-21 10:52:38

{:5_102:}

siazb8590 发表于 2023-7-28 10:19:12

我来学习啦

auend 发表于 2023-7-28 16:02:05

这个有意思 。

Mr.roushan 发表于 2023-8-10 11:44:53

看看

nkysp 发表于 2023-8-20 11:52:54

好

sharp46 发表于 2023-12-9 22:55:22

{:5_106:}

hejiage 发表于 2024-1-4 16:37:01

今天又多学习了一个

kittennnn 发表于 2024-1-19 12:20:47

{:5_109:}

kalendd 发表于 2024-2-17 21:29:01

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

dou820 发表于 2024-4-8 00:21:07


太难了，还用到了数学里的定理
页: [1]
查看完整版本: 题目12：第一个拥有超过500个约数的三角形数是多少？