ABC190 D - Staircase Sequences の解説 [Ruby]

2 min read読了の目安(約1800字

問題へのリンク

https://atcoder.jp/contests/abc190/tasks/abc190_d

問題概要

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

制約

  • 1\leq N \leq 10^{12}
  • N は整数

解法

長さが奇数の数列の総和は、「中心の数」×「数列の長さ」で計算できる。

長さが偶数の数列の総和は、「中心の2数の和」×「数列の長さ÷2」で計算できる。

これらから、整数からなる公差 1 の等差数列は、どんなものでも、 2 数の掛け算により総和を計算することができる。

逆に、 2 数の掛け算から、その結果に総和が等しい数列を復元したい。
A\times B という掛け算があったとき、 A (掛けられる数)を「中心の数(2数の和)」、 B (掛ける数)を「数列の長さ(÷2)」に対応させていく。

「奇数」×「奇数」の場合は、「長さが奇数の数列」と「長さが偶数の数列」の両方が復元できる。

「奇数」×「偶数」の場合は、「長さが偶数の数列」が復元できる。

「偶数」×「奇数」の場合は、「長さが奇数の数列」が復元できる。

「偶数」×「偶数」の場合は、数列が復元できない。

復元できる数列の数をまとめると以下のとおり。

掛けられる数 掛ける数 数列の数
奇数 奇数 2
奇数 偶数 1
偶数 奇数 1
偶数 偶数 0

なんとこれは掛け算に含まれる奇数の数に一致している!

すべての掛け算を列挙してみると、 N の約数がそれぞれ2回ずつ出てくるので、求める答えは N の約数に含まれる奇数の数の 2 倍」 である。

(例) N=12 の場合

(例) N=25 の場合

コード

require "prime"

# 約数を列挙した数列を返す関数
def divisor_enumeration(n)
  n.prime_division.inject([1]) do |ary, (p, e)|
    (0..e).map{ |e1| p ** e1 }.product(ary).map{ |a, b| a * b }
  end.sort
end

n = gets.to_i

# 約数のうち奇数であるものの数を2倍して出力
puts divisor_enumeration(n).count{|x| x.odd?} * 2

コードへのリンク

https://atcoder.jp/contests/abc190/submissions/19842475