Project Euler Problem 100

解法

青い玉の数:n
合計の玉の数:m
n*(n-1)/m*(m-1)=1/2
2(n*n-n)=m*m-m
2((n-1/2)^2-1/4) = (m-1/2)^2-1/4
2((2n-1)^2-1) = (2m-1)^2-1
(2m-1)^2 - 2(2n-1)^2 = -1

なのでベル方程式
x^2 - 2y^2 = -1
を解く

解の１つはx=29,y=41であることから順次解を構成していく。

ソースコード(C++)

x0,y0=3,2
x,y=41,29
loop do
  #次の解を求める
  x,y = x0*x+2*y0*y,x0*y+y0*x
  p [x,y]
  if x%2==1 && y%2==1
    m=(x+1)/2
    n=(y+1)/2
    if m>1e12 then
      puts n
      break
    end
  end
end