三角数问题....在4秒内显示

Question

通过添加自然数来生成三角数的序列.所以第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是第一个有超过五个除数的三角形数.

给定整数n,显示具有至少n个除数的第一个三角形数.

样本输入:5

输出28

输入约束:1 <= n <= 320

我显然能够做到这个问题,但我使用了一个天真的算法:

1. 获取ñ.

2. 找到三角形数字并使用mod运算符检查它们的因子数量.

但挑战是在输入后4秒内显示输出.在190和以上的高输入上,它花了将近15-16秒.然后我尝试将三角形数字及其因子数量先放入二维数组中,然后从用户处获取输入并搜索数组.但不知怎的,我无法做到:我遇到了很多处理器故障.请尝试使用此方法并粘贴代码.或者如果有更好的方法,请告诉我.

Answer 1

这是一个提示:

根据除数函数的除数的数量是每个素因子的幂加1的乘积.例如,让我们考虑28的指数素数表示:

28 = 2 ²*3 ⁰*5 ⁰*7 ¹*11 ⁰ ...

每个指数加1的乘积是:(2 + 1)*(0 + 1)*(0 + 1)*(1 + 1)*(0 + 1)... = 6,果然,28有6个除数.

现在,考虑第n ^个三角形数可以以闭合形式计算为n(n + 1)/ 2.我们可以简单地通过在每个位置加上指数来乘以指数素数形式的数字.除以2意味着减少两个地方的指数.

你知道我要去哪儿吗？