UVa 10642 -- Can You Solve It?

先不看題目，先關心一個問題：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))

http://uva.onlinejudge.org/external/106/10642.html

回到題目，擺明就是問 Cantor pairing function。簡單題得證。

通常反著問會困難許多，UVa 880，

如果直接計算會碰到 sqrt(8n+1)，這又牽涉到浮點數誤差問題，很煩。

程式：

https://github.com/Meng-Gen/UVa/blob/master/UVa/acm_10642.cc