2024年9月电子学会等级考试五级第三题——整数分解

题目

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需要空间大