歐拉計劃第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:

• 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?

高度可約的三角形數

三角形數數列是通過逐個加上自然數來生成的。例如，第7個三角形數是 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個約數的三角形數是多少？

解題思路

從 \(1\) 開始枚舉每一個數，判斷它有多少個約數。

判斷約數存在 \(O( \sqrt{n} )\) 時間複雜度的算法：

我們可以從 \(1\) 到 \(\lfloor \sqrt{n} \rfloor\) 去枚舉每一個數 \(i\)，如果 \(i\) 能整除 \(n\)，則 \(\frac{n}{i}\) 也能夠整除 \(n\)。

#include <bits/stdc++.h>
using namespace std;
int cal(long long n) {
    int cnt = 0;
    for (long long i = 1; i*i <= n; i ++) {
        if (n % i == 0) {
            if (i*i == n) cnt ++;
            else cnt += 2;
        }
    }
    return cnt;
}
int main() {
    int n = 0;
    for (long long i = 1; ; i ++) {
        n += i;
        if (cal(n) > 500) {
            cout << n << endl;
            break;
        }
    }
    return 0;
}