Instead of brute force is there any trick or formula to solve this problem.
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36
With brute force you have to memoize the result also. So that you can use the previously calculated result without needing to calculate again.