PAT (Advanced Level) Practice 1103 Integer Factorization

傷城~ 2023-07-03 02:42 16阅读 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;
    }