统计不同的连续数段

根据累加和的计算公式得到--最长数段中数字的个数k，然后再从2遍历到k（只有该范围个数的数字累加才有可能出现和等于n）：

可以通过计算，得到每个数段中可能的最小值，可以直接从该最小值开始查找。

 1 #include <iostream>
 2 #include <cmath>
 3 
 4 using namespace std;
 5 
 6 void Print(int a,int m) {
 7     for (int i = 0; i < m; i++)
 8         if (i == 0)
 9             cout << a + i;
10         else
11             cout << " + " << a + i;
12     cout << endl;
13 }
14 
15 int Sum_number(int n) {
16     int k = sqrt(2 * n), benchmark = 0, space = 0,ans = 0;    // 基准数，最大间隔数，连续数段个数
17     for (int i = 2; i <= k; i++) {        // i是每个数段的数字个数
18         benchmark = n / i;        // 每个连续数段都必有一个基准数，可直接求出基准数
19         space = benchmark - i / 2;    // 只有基准数间距之内的数相加才有可能相等
20         int j = space, sum = 0;
21         while ( 1 ) {    // 在基准数附近查找满足要求的数段，可直接用(a1 + an) * m / 2计算
22             sum = (j + (j + i - 1)) * i / 2;
23             if (sum < n)
24                 j++;
25             else if (sum == n) {
26                 ans++;    // 找到了对应数段
27                 Print(j, i);
28                 break;
29             }
30             else
31                 break;
32         }
33     }
34     return ans;
35 }
36 
37 int main()
38 {
39     int n;
40     cin >> n;
41     cout << Sum_number(n);
42     return 0;
43 }

2021-04-30