atcoder abc190 D - Staircase Sequences

約数 等差数列 AtCoder

問題

D - Staircase Sequences

整数からなる公差 1 の等差数列のうち、総和が N であるものはいくつあるでしょうか？

解法

等差数列の和は以下で求められる

$ s = (初項 + 末項) * 数列の長さ / 2 $

公差が1となっているので、 $ 数列の長さ = 末項 - 初項 + 1 $ と置ける。

$ s = (初項 + 末項)(末項 - 初項 + 1) / 2 $

$ 2s = (初項 + 末項)(末項 - 初項 + 1) $

$ X, Y $ を以下のように定義すると

$ X = (初項 + 末項) $

$ Y = (末項 - 初項 + 1) $

$ 2s = XY $ とでき、X, Y のすべての組み合わせを数える問題にできた。

X, Y は 2s の約数となるので2sの約数をすべて試せば良い。 ただし、初項と末項は整数である必要があるため、約数かつ、初項及び末項が整数となる場合をすべて数え上げれば良い。

$ 初項 = (X-Y+1) / 2 $

$ 末項 = (X+Y-1) / 2 $

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0;i<n;i++)

int main() {
  ll n;
  cin >> n;

  ll n2 = n*2, ans = 0;
  ll sq = sqrt(n2);
  // 約数を平方根までチェックする
  for (ll x = 1; x <= sq; x++) {
    if (n2 % x) continue; // 約数ではない

    ll y = n2/x;
    bool ok = (x+y-1) % 2 == 0 && (x-y+1) % 2 == 0;
    if (ok) ans += x==y ? 1 : 2; // x==yの場合は1通り
  }

  cout << ans << endl;
  return 0;
}

雑感

これで茶diffなのは結構しんどい