求HDUACM2058算法啊。。不要代码

2024-11-22 01:05:22
推荐回答(1个)
回答1:

中心思想是利用等差数列的公式进行计算,并根据公式的变形进行优化。
这里要用到的公式:S=a*n + n*(n-1)/2。
先考虑优化,因为暴力枚举可能的a和n的话,时间复杂度比较高。
根据上述公式,已知S就是题目中的m,项数n和m之间的关系可以表示为n^2 + an - 1 = 2m。已知a是正整数,那么可以得到n接下来的计算,围绕枚举n求a,再将a代入上述公式计算出结果与m比较展开,过程很简单,一共没几行代码。