P1147 连续自然数和

题目描述：P1147 连续自然数和

---

解题思路

---

• 解题思路

  1、题目要求 $l + (l+1) + (l+2) + \ldots + (r-1) + r = M$，可利用等差数列化简：$\frac{(首项 + 末项) * 项数}{2}$，即该题求所有满足 $(l + r)(r - l + 1) = 2M$ 的 $l, r$
  2、等式左侧为两个整数，所以左侧的 $(l + r)$ 和 $(r - l + 1)$ 必然都是 $2M$ 的因数。此时求出 $2M$ 的所有因数(记因数至 $x[]$ 数组)，便可将数据范围缩小至 $2\sqrt{2M}$ 之内
  3、由于直接枚举 $l, r$ 范围太大，而 $x[]$ 的下标范围显然更小。所以令 $x[i] = l + r$ ，$x[j] = r - l + 1$，联立整理两式得 $r = \frac{(x[i] + x[j] + 1)}{2}$，$l = x[i] - r$，此时 $l, r$ 为答案
  4、但要使得答案存在，则必须满足前述的 $l, r$ 为整数这一条件，参照两个化简式，需要使 $r$ 为整数。所以必须满足 $(x[i] + x[j] + 1)$ 为 $2$ 的倍数

---

代码实现

---

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  void solve()
  {
      int m;
      cin >> m;
  
      // 求 2 * M 的所有因子
      vector<int> x; // 记录 2 * M 的所有因子
      for (int i = 2; i <= 2 * m / i; i++)
      {
          if (2 * m % i)
              continue;
  
          x.push_back(i); // 小因子
          if (i != 2 * m / i)
              x.push_back(2 * m / i); // 大因子
      }
  
      // 枚举答案
      vector<pair<int, int>> ans;
      for (auto &xi : x)
      {
          for (auto &xj : x)
          {
              // 如果不满足整数条件
              if ((xi + xj - 1) % 2)
                  continue;
  
              int r = (xi + xj - 1) / 2, l = xi - r;
              // 判断 l, r 是否合法
              if (l >= 0 && l <= r && (l + r) * (r - l + 1) == 2 * m)
                  ans.push_back({l, r});
          }
      }
  
      // 排序输出
      sort(ans.begin(), ans.end());
      for (auto &[l, r] : ans)
          cout << l << ' ' << r << '\n';
  }
  
  int main()
  {
      ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

页底评论

---