1103 Integer Factorization （30 分)

2019-04-20

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:

1	N = n[1]^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 122+42+22+22+12, or 112+62+22+22+22, 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 { a1,a2,⋯,a**K } is said to be larger than { b1,b2,⋯,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:

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

Sample Input 2:

169 167 3

Sample Output 2:

1	Impossible

作者: CHEN, Yue

单位: 浙江大学

时间限制: 1200 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

给出N，K，P，要求将N分解为K个数的P次幂

分析

dfs暴力求解。由大到小，最大值为√(N-k-1)[实际上是p次方根，此时剩余k-1个数全为1]。通过upbound参数，控制本次选的数不能大于上一次选的，从而实现选的数非递增排序。findres的参数分别为剩余的n，已有数字个数，保存已有数字的vector，当前数字上限，已有数字和。剪枝规则如下：
1.当剩余的n恰好等于k-cnt时，说明余下的数字全为1。
2.当n小于0或者已有数字大于k个时，返回
3.当n等于0且恰有k个数，比较和，更新结果。

然后从upbound开始，依次判断。x为当前数的p次。假设选取当前数。则剩余k-cnt-1个数的最大值需大于n-x，最小值需小于n-x。符合条件才继续搜索。

代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <deque>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <sstream>

using namespace std;
int n, k, p, up, maxsum = -1;
vector<int> po;
vector<int> res;

void findres(int n, int cnt, vector<int> v, int upbound, int sum) {
    if (n == k - cnt) {
        for (int i = 0; i < n; i++)
            v.push_back(1);
        sum += n;
        if (sum > maxsum) {
            maxsum = sum;
            res = v;
        }
        return;
    }
    if (n < 0||cnt>k)
        return;
    if (cnt == k && n == 0) {
        if (sum > maxsum) {
            maxsum = sum;
            res = v;
        }
        return;
    }
    for (int i = upbound; i >= 1; i--) {
        int x = po[i];//x为i的p次
        if (n - x >= 0)
            if ((n - x) <= (k - cnt - 1) * x)//剩余数的最大值要大于n-x
                if ((n - x) >= (k - cnt - 1)) {//剩余数的最小值要小于n-x
                    v.push_back(i);
                    findres(n - x, cnt + 1, v, i, sum + i);
                    v.pop_back();
                }
    }
}

int main() {
    cin >> n >> k >> p;
    up = sqrt(n - k + 1);
    po.resize(up + 1);
    for (int i = 1; i <= up + 1; i++)
        po[i] = pow(i, p);
    vector<int> temp;
    findres(n, 0, temp, up, 0);
    if (maxsum == -1)
        cout << "Impossible" << endl;
    else {
        cout << n << " = ";
        int f = 0;
        for (int i:res) {
            f++ == 0 ? cout << "" : cout << " + ";
            cout << i << "^" << p;
        }
        cout << endl;
    }
    return 0;
}