Given an integer and an exponent, you must search for a combination of distinct positive integers that, when raised to the given exponent, add up to the given integer. For example, there are three ways of expressing 91 as the sum of perfect squares.
91 = 12 + 22 + 32 + 42 + 52 + 62
91 = 12 + 42 + 52 + 72
91 = 12 + 32 + 92
On the other hand 7, for example, cannot be expressed as the sum of distinct perfect squares.
Write a program which takes an integer and an exponent as input and finds a collection of distinct positive integers which when raised to the given exponent add up to the given integer. The program needs to produce only one collection of numbers, not all possible ones. If all possibilities are exhausted, conclude that no such sum exists.
The input consists of a pair of positive integers, the number to be represented as a sum of like powers (any number from 1 to 40000) and the exponent to be used (any exponent from 2 to 10). For example the input may be
881 3
The output is a list of distinct positive integers which, when individually raised to the specified power and summed, add up to the given integer. The integers may be in any order. The above input may lead to the following output:
3 5 9
because 881 = 33 + 53 + 93 If there is no solution for a specified number and power, then your program should write the message "No solution". For example, this input:
883 4
should produce this output:
No solution