纯情活泼的拆分

更好的阅读体验：

链接：https://pan.baidu.com/s/1o4smgWB19XF7_N_0SJ1R9Q ，提取码：dkq4 。

琪露诺学会了 $\mathtt{A+B\ problem}$ 和 $\mathtt{A^B\ problem}$ 。所以琪露诺打算将一个数进行拆分，来练习她学会的内容。以下会把这种拆分方式称作「纯情活泼的拆分」。

具体来说，她会把一个正整数 $\delta$ ，拆分成若干个互不相同的大于等于2的自然数的幂次和，即：

$\delta=p_1^{c_1}+p_2^{c_2}+\cdots =\sum p_i^{c_i}$

很显然地，对于一个 $\delta$ 可能存在若干种不同的拆分方式。为此，琪露诺定义了一个「纯情」值 $\varphi_\delta(p_1:c_1,p_2:c_2,\cdots)$ ，用于衡量一种拆分的价值。有：

$\varphi_\delta(p_1:c_1,p_2:c_2,\cdots)=c_1+c_2+\cdots =\sum c_i$

显然，对于每个 $\delta$ ，存在一种拆分方式使得它的「纯情」值最大，我们将这个最大值记为 $\delta$ 的「活泼」值，用 $\Phi(\delta)$ 表示。特别地，如果不存在任何一种合法的拆分方式，则 $\Phi(\delta)=9$ 。琪露诺为了验证她的拆分，找到了 $\mathit n$ 个数 $w_1,w_2,\cdots w_n$ 。你要做的就是分别求出 $\Phi(w_1),\Phi(w_2),\cdots \Phi(w_n)$ 。

#include<bits/stdc++.h> #define N 2000005 #define ll long long #define mp make_pair #define fi first #define se second using namespace std; int T,tp;ll ans[N],val[N],t[N]; priority_queue<pair<ll,ll>>q; ll rd(){ char c;ll re=0; while(!isdigit(c=getchar())); while(isdigit(c))re=re*10ll+c-'0',c=getchar(); return re; } int main(){ q.push(mp(-2,2)),T=2,val[2]=1ll; while(!q.empty()){ ll v=-q.top().fi,x=q.top().se;q.pop(); tp++;ans[tp]=ans[tp-1]+v;t[x]++,val[x]*=x; if(ans[tp]>1e12)break; if(x<=1e18/val[x])q.push(mp(-val[x]*(x-1ll),x)); if(q.empty()||-q.top().fi>T)T++,q.push(mp(-T,T)),val[T]=1ll; } int TT=rd(); while(TT--){ ll x=rd(); cout<<upper_bound(ans+1,ans+tp+1,x)-ans-1<<'\n'; } return 0; }

详情