先不看題目，先關心一個問題：the set of all rational numbers is countable.
http://en.wikipedia.org/wiki/Countable
The Cantor pairing function assigns one natural number to each pair of natural numbers.
這樣就能證明有理數是可數的 ((當然還有其他證明，請看 Royden, Real Analysis))
回到題目，擺明就是問 Cantor pairing function。簡單題得證。
通常反著問會困難許多，UVa 880，
如果直接計算會碰到 sqrt(8n+1)，這又牽涉到浮點數誤差問題，很煩。
程式：
沒有留言:
張貼留言