题目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 *****
这是我的代码：
#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))， 不知道算对没有，我用了质数筛优化的，但跑得很快。 我这个蒟蒻的算法居然和版主的算法差不多{:10_257:} zhangjinxuan 发表于 2023-7-4 19:16
我这个蒟蒻的算法居然和版主的算法差不多
{:10_282:} {:9_227:} 有你精彩，努力更新 {:5_102:} 我来学习啦 这个有意思 。 看看
好 {:5_106:} 今天又多学习了一个 {:5_109:} 太难了，还用到了数学里的定理
太难了，还用到了数学里的定理 1111 1
页:
[1]