Project Euler Problem 206

問題

Problem 206 - Project Euler

解法

下の桁から決めていき，おかしな所があったら枝刈りする

実装(Ruby)

STR="1_2_3_4_5_6_7_8_9"
def check(v)
	v=v.to_s
	return false if v.length!=STR.length
	STR.length.times{|i|
		next if i%2==1
		return false if(v[i]!=STR[i])
	}
	return true
end
def check2(v)
	v=v.to_s
	return false if v.length>STR.length
	((v.length+1)/2).times{|i|
		return false if(v[v.length-i*2-1]!=STR[STR.length-i*2-1])
	}
	return true
end

def solve(now,t)
	if check(now*now)
		p now.to_s+"0"
		exit
	end
	return if t*t>19293949596979899
	return if now*now>19293949596979899
	for i in 0..9
		solve(i*t+now,t*10) if check2(((i*t+now)**2)%(t*10))
	end
end
solve(0,1)