1103 Integer Factorization

The K−P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K−P factorization of N for any positive integers N, K and P.

Each input file contains one test case which gives in a line the three positive integers N (≤), K (≤) and P (1). The numbers in a line are separated by a space.

For each case, if the solution exists, output in the format:

where <code>n[i]</code> (<code>i</code> = 1, ..., <code>K</code>) is the <code>i</code>-th factor. All the factors must be printed in non-increasing order.

Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 1, or 1, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen -- sequence { , } is said to be larger than { , } if there exists 1 such that a​i​​=b​i​​ for i&lt;L and a​L​​&gt;b​L​​.

If there is no solution, simple output <code>Impossible</code>.

題意：

　　給出一個數字，問這個數字能不能由k個不同數字（N[k]）的p次方相加得到。如果存在多種可能，則輸出N[k]之和最大的那個，如果仍然相等，則輸出則輸出下标相同時值大的那一個。

思路：

　　正确的解法是使用DFS + 剪枝。

　　預處理： 将 i * i &lt;= n 的所有可能存儲到數組v[]中這裡v中存儲的數字是 i * i。

　　深度優先搜尋： DFS(int index, int tempSum, int tempK, int facSum)各參數代表的含義：

　　　　　　　　　 index：代表預處理數組的下标； tempSum：代表目前已處理數字之和； tempK：代表已經處理的數字的個數； facSum：DFS調用到本層時所累加數字之和。

　　　　　　　　　 遞歸跳出的條件是：index &gt;= n, 代表已經周遊完了所有的可能。 當tempK == K的時候，if (tempSum == n &amp;&amp; facSum &gt; maxFaxSum) 說明結果需要進行更新。（ans = tempAns）

　　　　　　　　　 ans用來表示結果的因子序列，tempAns用來表示目前周遊的因子序列。

Code：

看着别人的代碼，自己一邊想一邊寫總算是把這道題給解決了，而且送出也通過了。但是為什麼樣例的輸出和代碼得輸出不一樣呢？

樣例的輸出是：

代碼得輸出是：

更神奇的是代碼送出了之後還都通過了所有的樣例？？？？？？？？？？

2020-07-12 22:05:00

剛才又在我這台機器上（Linux）輸出了一下發現結果有和測試樣例一樣了，有時間再到（Windows）上試一下，看一下結果是不是還是一樣的。

永遠渴望，大智若愚（stay hungry, stay foolish）