💎

ABC190 D - Staircase Sequences の解説 [Ruby]

2021/01/31に公開

Ruby

問題へのリンク

問題概要

整数からなる公差 $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

ABC190 D - Staircase Sequences の解説 [Ruby]

問題へのリンク

問題概要

制約

解法

コード

コードへのリンク

Discussion