三角数:第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,所以这个算法在时间上占优。