题目
3、整数分解
正整数 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
代码
#include <bits/stdc++.h>
#include <windows.h>
using namespace std;
struct node{
int num,//因数
x;//底数
bool operator<(const node &b)const{return num>b.num;}
//重载<比较运算符，定义比较规则。这里是反序，大了才小（sort默认<升序，这里改成降序）
//第一个const是常量引用，第二个是不修改该成员变量
};
int n,k,p,ans=0;
vector<node> ans_v,v;//最终因数和深搜时因数
void view(string s,const vector<node> &v){
cout<<s<<endl;
for(auto x=v.begin();x!=v.end();x++)
if(x==v.begin())cout<<n<<":"<<x->x<<"^"<<p;
else cout<<"+"<<x->x<<"^"<<p;
cout<<endl;
//Sleep(3000);
}
//bool go(剩因数和,剩几个数,上个因数){
void go(int he,int left,int num){
if(he<0||left<0||he>0&&left==0||he==0&&left){//剪枝
cout<<endl;return;
}
cout<<"出发状态:"<<he<<"\t"<<left<<endl;
if(he==0&&left==0){//到达目标状态，凑够了
view("again",v);
int sum=0;
sort(v.begin(),v.end());
for(auto i=v.begin();i!=v.end();i++)sum+=i->x;//因数底数和
cout<<sum<<"\t"<<ans<<endl;
if(sum<ans)return;//因数底数和小了
else if(sum==ans){//一样则用字典序高
bool k=1;
for(vector<node>::iterator i=v.begin(),j=ans_v.begin();i!=v.end();i++,j++)
if(i->x>j->x)break;
else if(i->x<j->x){k=0;break;}
if(k)ans_v=v;
else return;
}else{
ans_v=v,ans=sum;
view("ok",v);
}
}
for(int x=he;x>0;x--){//遍历因数
int d=pow(x,1.0/p); //开方计算求底数
if(pow(d,p)!=x)continue;//不能开方
if(x>num)continue;//剪枝重复情况，10+5和5+10是同种情况，这里只要降序
if(x*left<he)break;//剪枝凑不够情况，剩的全是最大因数都不够凑目标数
cout<<"分出"<<x<<";";
v2.push_back({x,d});
go(he-x,left-1,x);//继续对剩余数拆解因数
v2.pop_back();//回溯
}
}
int main(){
freopen("data.cpp","r",stdin);
cin>>n>>k>>p;
go(n,k,n);
if(ans==0)cout<<"imposibel";
else {
for(auto i=ans_v.begin();i!=ans_v.end();i++){
if(i==ans_v.begin())cout<<n<<"="<<i->x<<"^"<<p;
else cout<<"+"<<i->x<<"^"<<p;
}
}
return 0;
}
分析
- 是k个数的和，
- 而且每个数都是p次幂
- 各因子的和最大
- 和相同，选择字典序最大
- 指数运算（乘方运算） 2^4=16 底数2， 指数4， 幂是16
- 开放运算 pow(16,-1.0/4) 底数16，指数1.0/4 根是2
- 剪枝条件：如果当前因数乘以剩余个数少于剩余总和，则跳过该值。
结果
会有多组解，
留下因数底数和最大的
一样大的，留下字典序高的
小结
分层解决问题
先解决因数和的事情
再解决开方的问题
然后是因数和
后是字典序
该问题状态都，用BFS需要空间大