# The power sum challenge

Find the number of ways that a given integer, , can be expressed as the sum of the power of unique, natural numbers.

**Input Format**

The first line contains an integer .

The second line contains an integer .

**Constraints**

**Output Format**

Output a single integer, the answer to the problem explained above.

**Sample Input 0**

10 2

**Sample Output 0**

1

**Explanation 0**

If and , we need to find the number of ways that can be represented as the sum of squares of unique numbers.

This is the only way in which can be expressed as the sum of unique squares.

**Sample Input 1**

100 2

**Sample Output 1**

3

**Explanation 1**

**Sample Input 2**

400 2

**Sample Output 2**

55

**Solution**

public class ThePowerSum { private static int solve(int x, int n, int num, double sum) { if (sum == x) { return 1; } else { int ans = 0; if (sum < x) { for (int i = num; i <= Math.pow(x, 1.0 / n); i++) { ans += solve(x, n, i + 1, sum + Math.pow(i, n)); } } return ans; } } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt")); Scanner in = new Scanner(System.in); int x = in.nextInt(); int n = in.nextInt(); System.out.println(solve(x, n, 1, 0)); } }