PAT (Advanced Level) Practice 1103 Integer Factorization-蒲公英云

PAT (Advanced Level) Practice 1103 Integer Factorization

傷城~ 2023-07-03 02:42 117阅读 0赞

回溯就可以解，记一个坑，在计算a的n次方时，如果你需要的是整数，最好不要用pow，而是自己写一个。

我的编译器使用pow的时候，如果传的值不是double类型的而是int类型的数值，会产生比较大的误差，如10的2次方可能的出的结果就是99，而非100。

还有，自己写的pows不会超时，而使用pow函数会有个测试点超时。

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int n,k,p,m,maxn=-999;
vector<int> temp,result;
int pows(int a,int e){
    int sum =1;
    while(e!=0){
        sum=sum*a;
        e--;
    }
    return sum;
}
void f(int i){
    if(k<0) return;
    if(k==0&&n==0){
        bool larger=false;
        int sum=0;
        for(int j=0;j<temp.size();j++){
            sum+=temp[j];
            if(result.size()!=0&&temp[j]>result[j]) larger=true;
        }
        if(sum>maxn ||(sum==maxn&&larger)){
            result=temp;
            maxn=sum;
        }
        return;
    }
    for(int h=i;h<=m;h++){
        int facor=pows(h,p);
        if(n-facor>=0){
            n-=facor;
            k--;
            temp.push_back(h);
            f(h);
            temp.pop_back();
            n+=facor;
            k++;
        }else{
            return;
        }
    }
}
int main()
{
    cin>>n>>k>>p;
    int tn=n;
    for(int i=1;i<=n;i++){
        if(pows(i,p)>=n){
            m=i;//阈值
            break;
        }
    }
    f(1);
    if(result.size()==0){
        cout<<"Impossible"<<endl;
    }else{
        cout<<tn<<" = ";
        for(int i=result.size()-1;i>=0;i--){
            cout<<result[i]<<"^"<<p;
            if(i!=0){
                cout<<" + ";
            }
        }
    }
    return 0;
}