|
|
back to boardAccepted simple approach for this problem It is easy to solve this problem by using such recursive formula (k+1)P_k(N)=(N+1)^(k+1)-1-sum_(l=0)^(k-1) C_(k+1)^l P_l(N), where P_k(N) is a sum of powers k from 1 up to N, C_k^l is a binomial coefficient. I assume that P_0(N)=N. You can check this formula by summing up from 1 to N following identities (n+1)^k-n^k=sum_(l=0)^(k-1) C_k^l n^l. However, P_k(x) has non-integer coefficients, so it is better to introduce polynomials Q_k(x) by formula Q_k(x)=(k+1)!P_k(x). It can be proven by induction based on recursive formula above that Q(x) has integer coefficients!!! So, use BigIntegers in Java, otherwise you would have overflow. Good luck! Edited by author 08.05.2017 19:44 Edited by author 08.05.2017 19:44 Another accepted simple approach You can make a system of linear equations with k+2 variables and equations, which would look like: A_0 * 1^0 + A_1 * 1^1 + ... + A_(k+2) * 1^(k+2) = 1^k A_0 * 2^0 + A_1 * 2^1 + ... + A_(k+2) * 2^(k+2) = 2^k ... A_0 * (k+2)^0 + A_1 * (k+2)^1 + ... + A_(k+2) * (k+2)^(k+2) = (k+2)^k So, you only need to find A_i coefficients using Gaussion elimination. |
|
|