secondEquation.rb

# bを固定したときの(a,c)の組み合わせを数える
# cnt_ac_combs(3) => 3 [(a,c) = (1,1)(1,2)(2,1)]
def cnt_ac_combs(b)
	t = b ** 2 / 4
	cnt = 0 # a < c
	(1..t).each{|a| a * (a + 1) > t ? break : cnt += t / a - a}
	cnt * 2 + Math.sqrt(t).to_i
end

# 1 <= b <= m を満たす(a,b,c)の組み合わせの総数を数える
# cnt_abc_combs => 4 [(a,b,c) = (1,2,1)(1,3,1)(1,3,2)(2,3,1)]
def cnt_abc_combs(m)
	(1..m).inject(0){|sum, b| sum + cnt_ac_combs(b)}
end

p cnt_abc_combs 3000

__END__

方程式 a * x ** 2 + b * x + c = 0 が実数解を少なくともひとつ持つ条件は
	b ** 2 - 4 * a * c >= 0
		<=> b ** 2 >= 4 * a * c
		<=> b ** 2 / 4 >= a * c
ここで t = b ** 2 / 4 とおくと t >= a * c
bを固定したとき、tもただひとつに決まるから、bを1..mの範囲で動かしながら
t >= a * c を満たす(a,c)の組み合わせを数え上げればよい

t >= a * c を満たす(a,c)の組み合わせをいかに効率よく数えるか
仮に t = 7 とすると、aとcの取る範囲はそれぞれ 1 <= a <= 7, 1 <= c <= 7 である
ここで行がa、列がc、要素が a * c であるような表/配列を考える
 1  2  3  4  5  6  7
 2  4  6  8 10 12 14
 3  6  9 12 15 18 21
 4  8 12 16 20 24 28
 5 10 15 20 25 30 35
 6 12 18 24 30 36 42
 7 14 21 28 35 42 49
これを3つにわけて考える。まずは a < c の場合
 2  3  4  5  6  7  => cの取りうる範囲は2..7 => 7 - 2 + 1 = 6個
    4  6  8 12 14  => cの取りうる範囲は3..4 => 4 - 3 + 1 = 2個
      12 15 18 21  => a * c の最小値が12でt=7を超えている。よって以降は調べない
         20 24 28
            30 35
               42
次に a = c の場合
 1
    4
       6
         12
            16
               25
                  36
                     49
a = c = 1, a = c = 2, a = c = 3 のとき t >= a * c を満たす => 3個
最後に a > c の場合だが、これは a < c の場合と対称より、組の個数は同じである
以上よりt = 7 のときの(a,c)の組み合わせの総数は　(6 + 2) * 2 + 3 = 19個　となる

以上を一般化すると、あるtについてt >= a * c を満たす(a,c)の組み合わせの総数は次のようにもとめられる
1. a < c
	aを固定して、t >= a * c を満たすcの総数を数え上げる : c_max - c_min + 1 = t / a - (a + 1) + 1 = t / a - a
	ただしaを1ずつ大きくしていくが、a * c の最小値、つまり a * (a + 1) がtを超えた場合
	以降 a * c が t を下回ることはないので、探索/ループを打ち切る。
2. a = c
	a = c の最小値は1で、最大値は sqrt(t).floor : sqrt(t).floor - 1 + 1 = sqrt(t).floor
3. a > c
	対称性を考えると a < c の場合と個数は同じ
よってt >= a * c を満たす(a,c)の組み合わせの総数は comb_a<c * 2 + comb_a=c となる