首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#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&lt;bits/stdc++.h&gt; 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 &lt; b; i++)    res *= a;     return res; } int main() {     cin &gt;&gt; n &gt;&gt; k &gt;&gt; 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 &gt; n) break;  //如果当前枚举的数已经超过n,则dp结束         //更新数据         for (int i = 0; i &lt;= n; i++)             for (int j = 0; j &lt;= k; j++)             {                 //不选当前数                 f[m][i][j] = f[m - 1][i][j];                 //选当前数                 if (i &gt;= v &amp;&amp; j) f[m][i][j] = max(f[m][i][j], f[m][i - v][j - 1] + m);             }     }     m--;     //从得到的集合中开始拆分出答案     if (f[m][n][k] &lt; 0)    puts("Impossible");     else     {         printf("%d = ", n);         bool is_first = true;         while (m)         {             int v = power(m, p);             //判断答案集合中是否有m             while (n &gt;= v &amp;&amp; k &amp;&amp; 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>
这道题暂未补解析。