1103. Integer Factorization.md

pat 甲级 1103. Integer Factorization

题意概述

从$[1,\sqrt[P] {N}$中选择 K 个数，使得他们的 P 次方和等于 N。

输入输出格式

输入给出三个正整数 N，K 和 P。一行中的数字用空格分隔。

对于每种情况，如果存在一种解决方案，使得$N=n[1]^P+\cdots+n[K]^P$，则以N = n[1]^P + ... + n[K]^P$格式输出，所有因子都必须按不升序打印。如果解不唯一，输出因子和最大的解。如果还不唯一，输出字典序最大的解。

数据规模

$$N<=400,K<=N,1<P<=7$$

算法设计

对于当前处理的数，根据选与不选这个数进入两个分支，然后进行暴力搜索并剪枝即可。具体实现可见代码。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
gg ni, ki, pi;
vector<gg> ans, temp, pows{0};
gg s = 0;
void dfs(gg n, gg k, gg num, gg sum) {
    if (k == 0 and n == 0 and sum > s) {
        ans = temp;
        s = sum;
        return;
    }
    if (k <= 0 or n <= 0 or num <= 0) {
        return;
    }
    temp.push_back(num);
    dfs(n - pows[num], k - 1, num, sum + num);
    temp.pop_back();
    dfs(n, k, num - 1, sum);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> ni >> ki >> pi;
    while (pows.back() < ni) {
        pows.push_back(pow(pows.size(), pi));
    }
    dfs(ni, ki, pows.size() - 1, 0);
    if (ans.empty()) {
        cout << "Impossible";
        return 0;
    }
    cout << ni << " = " << ans[0] << "^" << pi;
    for (gg i = 1; i < ans.size(); ++i) {
        cout << " + " << ans[i] << "^" << pi;
    }
    return 0;
}