简答题
偏难
#7554
整数分解 正整数 N 的 K-P 分解是指将 N 写成 K 个正整数的 P 次方的和。本题就请你对任意给定的正整数 N、K、P,写出 N 的 K-P 分解。 时…
整数分解
正整数 N 的 K-P 分解是指将 N 写成 K 个正整数的 P 次方的和。本题就请你对任意给定的正整数 N、K、P,写出 N 的 K-P 分解。
时间限制:8000
内存限制:262144
输入
输入在一行给出 3 个正整数 N (≤ 400)、K (≤ N)、P (1 < P ≤ 7),以空格分隔。
输出
如果存在解,则按下列格式输出: N = n[1]^P + ... n[K]^P 其中 n[i] (i = 1, ..., K) 是第 i 个分解因子。所有的分解因子要按非增顺序输出。 注意:解可能是不唯一的。例如 169 的 5-2 分解就存在 9 个解,如 12^2 + 4^2 + 2^2 + 2^2 + 1^2 或 11^2 + 6^2 + 2^2 + 2^2 + 2^2 等等。你必须输出分解因子和最大的那个解。如果还不唯一,则输出具有最大的分解因子序列的解 —— 我们称序列 { a1, a2, … , aK } 比序列 { b1, b2, … , bK } 大,如果存在 1 ≤ L ≤ K 使得 ai=bi 对于 i < L 成立,并且有 aL > bL。 如果解不存在,则输出 `Impossible`。
样例输入
样例#1:
169 5 2
样例#2:
169 167 3
样例输出
样例#1:
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
样例#2:
Impossible
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<bits/stdc++.h>
using namespace std;
const int N = 410;
int n, k, p;
int f[21][N][N];
//计算a的b次方
int power(int a, int b)
{
int res = 1;
for (int i = 0; i < b; i++) res *= a;
return res;
}
int main()
{
cin >> n >> k >> p;
//初始化
memset(f, -0x3f, sizeof f);
f[0][0][0] = 0;
//开始dp
int m;
for (m = 1;; m++) //从1开始向后枚举
{
int v = power(m, p); //计算m的p次方
if (v > n) break; //如果当前枚举的数已经超过n,则dp结束
//更新数据
for (int i = 0; i <= n; i++)
for (int j = 0; j <= k; j++)
{
//不选当前数
f[m][i][j] = f[m - 1][i][j];
//选当前数
if (i >= v && j) f[m][i][j] = max(f[m][i][j], f[m][i - v][j - 1] + m);
}
}
m--;
//从得到的集合中开始拆分出答案
if (f[m][n][k] < 0) puts("Impossible");
else
{
printf("%d = ", n);
bool is_first = true;
while (m)
{
int v = power(m, p);
//判断答案集合中是否有m
while (n >= v && k && f[m][n - v][k - 1] + m == f[m][n][k])
{
if (is_first) is_first = false;
else printf(" + ");
printf("%d^%d", m, p);
n -= v, k--;
}
m--;
}
}
return 0;
}</pre>
这道题暂未补解析。