问题描述

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[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
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_ifor i<L and a_L>b_L .
If there is no solution, simple output Impossible

解决方法

#include <stdio.h>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
vector<int> temp, fin;
int n = 0, k = 0, p = 0, loop = 0;
// 本身的时间复杂度太高  需要进行剪枝
bool cmp(int a, int b)
{
  return a > b;
}
int myPow(int n, int p)
{
  int res = n;
  for (int i = 1; i < p; i++)
  {
    res *= n;
  }
  return res;
}
int compare(vector<int> a, vector<int> b)
{
  int sum1 = 0, sum2 = 0;
  for (int i = 0; i < a.size(); i++)
  {
    sum1 += a[i];
    sum2 += b[i];
  }

  if (sum1 != sum2)
  {
    return sum1 - sum2;
  }
  else
  {
    for (int i = 0; i < a.size(); i++)
    {
      if (a[i] != b[i])
        return a[i] - b[i];
    }
    return 0;
  }
}
void seek(int index, int sumNum, int sumVal)
{
  if (sumVal == n && sumNum == k)
  {
    if (fin.size() == 0)
      fin = temp;
    else if (compare(fin, temp) < 0)
      fin = temp;
    return;
  }
  /*
    index >= loop || sumNum > k 原来写的
    通过sumVal >= n又减少了时间复杂度
  */
  if (index >= loop || sumNum > k || sumVal >= n)
  {
    return;
  }

  temp.push_back(index);
  seek(index, sumNum + 1, sumVal + myPow(index, p));
  temp.pop_back();
  /*
    程序本身最大的复杂度就在于递归的层数,通过
    (index + 1 <= loop) && (sumVal + myPow(index + 1, p) <= n)
    减少了递归的层数减少时间复杂度
  */
  if ((index + 1 <= loop) && (sumVal + myPow(index + 1, p) <= n))
  {
    seek(index + 1, sumNum, sumVal);
  }
}
int main(void)
{
  scanf("%d %d %d", &n, &k, &p);
  loop = sqrt(n) + 1;
  seek(1, 0, 0);
  if (fin.size() != 0)
  {
    printf("%d = ", n);
  }
  else
  {
    //注意没结果时只用输出Impossible即可
    printf("Impossible");
    return 0;
  }
  sort(fin.begin(), fin.end(), cmp);
  for (vector<int>::iterator it = fin.begin(); it != fin.end(); it++)
  {
    printf("%d^%d", *it, p);
    if (it + 1 != fin.end())
    {
      printf(" + ");
    }
  }
  return 0;
}

基本策略

• 基本的DFS搜索策略
• 问题在于如果不进行剪枝的话递归会使得程序超时,剪枝处已注释

结果展示

• PatA1103.png