PAT (Advanced Level) Practice - 1103 Integer Factorization（30 分）

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
intn,k,p,ans;
vector<ll>v, rsv, tv;
voiddfs(intsum, intl, intisum, intidx)
{
if(sum==n&&l==k&&isum>ans)
    {
ans=isum;
rsv=tv;
return;
    }
for(inti=idx;i>=1;i--)
    {
if(l+1>k||sum+v[i]*(k-l)<n) return; // 剪枝1if(sum+v[i]+v[1]*(k-l-1)>n) continue; // 剪枝2tv[l]=i;
dfs(sum+v[i],l+1,isum+i,i); // 剪枝3：最后一个是 i    }
}
intmain()
{
llval;
intidx=0;
scanf("%d%d%d",&n,&k,&p);
tv.resize(k);
while(idx<=n)
    {
val=ll(pow(idx,p)+0.5);
if(val>n) break;
v.push_back(val);
idx++;
    }
dfs(0,0,0,idx-1);
if(rsv.size()==0) puts("Impossible");
else    {
printf("%d = %lld^%d",n,rsv[0],p);
for(inti=1;i<rsv.size();i++)
printf(" + %lld^%d",rsv[i],p);
puts("");
    }
return0;
}
/* 容易TLE样例128 114 3285 157 2362 195 3*/