PAT_A1103#Integer Factorization

Source:

PAT A1103 Integer Factorization (30 分)

Description:

The K−P factorization of a positive integer N is to write N as the sum of the P-th power of Kpositive 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 (≤), K (≤) and P (1). 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 1, or 1, 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 { , } is said to be larger than { , } if there exists 1 such that ai=bifor i<L and aL>bL.

If there is no solution, simple output Impossible.

Sample Input 1:

169 5 2

Sample Output 1:

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

Sample Input 2:

169 167 3

Sample Output 2:

Impossible

Keys:

深度优先搜索（Depth First Search）

Attention:

不同的编译环境pow函数的精度不同，PAT跑的数据是对的，但我电脑上跑出来是错的，可以自己写一个

Code:

 /*

 time: 2019-07-02 18:55:08

 problem: PAT_A1103#Integer Factorization

 AC: 18:08

 题目大意：

 将整数N分解为以P为指数的K个因式的和

 输入：

 正整数N<=400，因式个数K，指数1<P<=7

 输出：

 按底数递减，

 若不唯一，打印底数和最大的一组，

 若不唯一，打印字典序较大的一组

 基本思路：

 深度优先搜索，至第K层时若存在解，则选择最优解

 */

 #include<cstdio>

 #include<vector>

 #include<cmath>

 using namespace std;

 int k,n,p,optValue=;

 vector<int> fac,temp,ans;

 void DFS(int index, int numK, int sum, int sumFac)

 {

     if(numK==k && sum==n && sumFac>optValue)

     {

         optValue = sumFac;

         ans = temp;

     }

     if(numK>=k || sum>=n || index<=)

         return;

     temp.push_back(index);

     DFS(index,numK+,sum+fac[index],sumFac+index);

     temp.pop_back();

     DFS(index-,numK,sum,sumFac);

 }

 int main()

 {

 #ifdef ONLINE_JUDGE

 #else

     freopen("Test.txt", "r", stdin);

 #endif // ONLINE_JUDGE

     scanf("%d%d%d", &n,&k,&p);

     for(int i=; pow(i,p)<=n; i++){

         fac.push_back(pow(i,p));

     }

     DFS(fac.size()-,,,);

     if(ans.size() == )

         printf("Impossible");

     else

     {

         printf("%d = %d^%d", n,ans[],p);

         for(int i=; i<ans.size(); i++)

             printf(" + %d^%d", ans[i],p);

     }

     return ;

 }

巴特西

PAT_A1103#Integer Factorization

Source:

Description:

Input Specification:

Output Specification:

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

Keys:

Attention:

Code:

最新文章

热门文章