100000012 - highly divisible triangular number

三角数:第i个三角数为前i个自然数之和。

前7个三角数依次是:1,3,6,10,15,21,28

它们分别有1、2、4、4、4、4、6个因子。

求,第一个因子个数超过n的三角数。

输入

n

测试点一:n=500

测试点二:n=1000

测试点三:n=1500

输出

样例

输入


                

输出


                

提示

a、直接枚举每个三角数,而后对其因数分解并计数。极限可以达到1s计算出测试点一。

b、枚举因子个数(极限可到达1s计算出测试点三):

预备知识:

1、约数和定理:一个数的因子个数等于其每个质因子个数+1而后相乘。如28=2^2×7^1,则其因子数量为(2+1)×(1+1)个。

2、相邻两数互质,即没有共同质因数。

根据三角数的通项公式t=n×(n+1)/2,结合前置知识2可知:

n和(n-1)没有相同的质因数。于是,通项公式可以表示为若干个质数幂相乘的形式:

2×t=(p_1^{x1}×p_2^{x2}×...)×(q_1^{y1}×q_2^{y2}×.....)

可知2×t的因子数为:

(x1+1)×(x2+1)×....×(y1+1)×(y2+1)....

记为:

x×y

若想得到t的因子数,只需要偶数时计数-1,因为奇偶交替出现。

显而易见,n与n+1的因子要比求它们乘积形式的三角数的因子要快,并且每次可以把n+1代替n,所以这个算法在时间上占优。

时间限制 500 毫秒
内存限制 128 MB
统计
上一题 下一题