1103. Integer Factorization (30)

題目如下：

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.

Input Specification:

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

Output Specification:

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

N = n₁^P + ... n_K^P

where?n_i?(i=1, ... K) is the i-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 12²?+ 4²?+ 2²?+ 2²?+ 1², or 11²?+ 6²?+ 2²?+ 2²?+ 2², 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 { a₁, a₂, ... a_K?} is said to be?larger?than { b₁, b₂, ... b_K?} if there exists 1<=L<=K such that a_i=b_i?for i<L and a_L>b_L

If there is no solution, simple output "Impossible".

Sample Input 1:

169 5 2

Sample Output 1:

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

Sample Input 2:

169 167 3

Sample Output 2:

Impossible

本題考察了DFS的回溯剪枝。

為了順應題目找到最大系數和或者最大系數列，我們從小到大進行枚舉，這樣即使碰到了和相等的情況，由于是遞增著枚舉的，因此直接覆蓋原來的系數列，得到的就是最終滿足條件的系數列。

我們利用DFS來從小到大的枚舉，DFS函數的參數如下：

dfs(long long N, int cur, vector<int>& factors);

①其中N是當前值，從最初的輸入開始，逐步減去每個系數的運算結果；cur是枚舉到的位置，從0開始，依次填入factors容器中，當cur==K時，枚舉已經結束，我們判斷N是否為0，為0則找到了一個滿足條件的系數列，并且這個系數列按照升序存儲在factors中。注意到cur==K但N≠0是我們的第一個剪枝條件。

②為了保證枚舉從小到大開始，在每次枚舉開始前計算lower和upper兩個值，其中lower由factors中剛剛枚舉完的上一個值確定，如果當前是枚舉的起始點，則從1開始；upper為根號下N，因為系數的次方P＞1，因此最大的系數不可能超過根號N。

③對lower到upper內的每一個值，計算系數的P次方，用res表示。如果N≥res，則說明合法，將其填入factors中并且向后枚舉，即

factors[cur] = i;
dfs(N-res,cur+1,factors);

如果N＜res，說明系數偏大，又因為系數是遞增枚舉的，所以此后都不滿足，直接返回，這是我們的第二個剪枝條件。

綜合上面兩個剪枝條件，即可寫出高效的dfs算法來枚舉結果，為了能得到滿足題目要求的系數列，我們設置全局變量nowSum和finalFactor，每次找到一個系數列，就求其系數和sum，如果sum≥nowSum，則更新nowSum與finalFactor，等號涵蓋了題目中的第二個條件，因為后面出現的系數列一定大于前面出現的系數列（遞增枚舉）。

最后如果finalFactor規模為K，則說明找到，先反轉，后輸出，注意格式；否則輸出Impossible。

代碼如下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>using namespace std;typedef long long lint;lint N,K;
int P;lint lpower(lint n, lint p){if(n == 1) return 1;int factor = n;for(int i = 1; i < p; i++) n *= factor;return n;
}vector<int> finalFactor;
int nowSum = 0;bool dfs(lint N, int cur, vector<int>& factors){if(cur == K){if(N == 0){int sum = 0;for(int i = 0; i < factors.size(); i++){sum += factors[i];}if(sum >= nowSum){finalFactor = factors;nowSum = sum;}return true;}else return false;}lint upper = sqrt((double)N);lint lower = cur > 0 ? factors[cur - 1] : 1;for(lint i = lower; i <= upper; i++){lint res = lpower(i,P);if(N >= res){factors[cur] = i;dfs(N-res,cur+1,factors);}else{return false;}}return true;
}int main()
{cin >> N >> K >> P;vector<int> factors(K);dfs(N,0,factors);reverse(finalFactor.begin(),finalFactor.end());if(finalFactor.size() == K){printf("%d = ",N);printf("%d^%d",finalFactor[0],P);for(int i = 1; i < finalFactor.size(); i++){printf(" + %d^%d",finalFactor[i],P);}}else{cout << "Impossible";}cout << endl;return 0;
}