PAT甲级——A1103 Integer Factorization
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=bi for 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
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int n, k, p, maxFacSum = -;//maxFacSum用来记录最大底数之和
vector<int>fac, ans, temp;//最大底数不超过n的数,底数最优数序列,临时存放
void DFS(int index, int nowK, int sum, int facSum)
{
if (sum == n && nowK == k)//统计因素个数
{
if (facSum > maxFacSum)//更优的组合
{
ans = temp;
maxFacSum = facSum;
}
return;
}
if (sum > n || nowK > k)return;//超出限制
if (index - >= )//给出数组小角标的限制
{
temp.push_back(index);//记录数据
DFS(index, nowK + , sum + fac[index], facSum + index);//选
temp.pop_back();//弹出数据
DFS(index - , nowK, sum, facSum);//不选
}
}
int main()
{
cin >> n >> k >> p;
for (int i = ; pow(i, p) <= n; ++i)
fac.push_back(pow(i, p));//初始化底数不超过n的因素
DFS(fac.size() - , , , );//为了得到最大的因素数组,从最后一位开始向前搜索
if (maxFacSum == -)
cout << "Impossible" << endl;//没有找到满足的序列
else
{
cout << n << " = ";
for (int i = ; i < ans.size(); i++)
cout << ans[i] << "^" << p << (i == ans.size() - ? "" : " + ");
}
return ;
}
最新文章
- Spring之旅
- .NET 数据类型转换 方法
- MySQL - 问题集 - 触发器更新本表数据异常";Can’t update table ‘tbl’ in stored function/trigger because it is already used by statement which invoked this";
- NTKO控件在阅读PDF时,显示DEMO的问题
- linux中touch命令参数修改文件的时间戳(转)
- zw版【转发&#183;台湾nvp系列Delphi例程】HALCON BinThreshold
- Hadoop Balance
- Verilog杂谈
- leetcode:Contains Duplicate和Contains Duplicate II
- css Hack,用IE11模拟测试的,条件注释要找真IE去测,模拟的无效
- cocos2d-x编程的一些小技巧
- WPF 弱事件
- soj 1700 ping_简单dp
- 整理网站优化(SEO)的方案
- memcached与.NET的融合使用2
- Linux入门:usermod - 修改用户帐户信息
- 分部类,分部方法 - 修饰符partial
- php使用sftp上传文件
- 使用DDMS中的内存监测工具Heap来优化内存
- textarea的placeholder属性内容折行显示(PC和移动端端)
热门文章
- Eclipse指定JDK版本
- linux命令重定向>;、>;>;、 1>;、 2>;、 1>;>;、 2>;>;、 <;(转)
- [JZOJ2866] 【集训队互测 2012】Bomb
- (20)Oracle函数
- quartz的job中注入spring对象!
- python 安装bs4
- python常用包及功能介绍
- <;jquery>;基本的模态框
- Hamilton回路 旅行商TSP问题 /// dp oj1964
- NEO4J全文检索架构