HBC222904[NOIP2003]侦探推理,枚举,NOIP复赛纯情活泼的拆分题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

更好的阅读体验： 链接：https://pan.baidu.com/s/1o4smgWB19XF7_N_0SJ1R9Q，提取码：dkq4， 琪露诺学会了 A+Bproblemmathtt{A+B problem}A+Bproblem 和 ABproblemmathtt{A^B problem}ABproblem ，所以琪露诺打算将

更好的阅读体验： 链接：https://pan.baidu.com/s/1o4smgWB19XF7_N_0SJ1R9Q ，提取码：dkq4 。 琪露诺学会了 A+B problemmathtt{A+B problem}A+B problem 和 AB problemmathtt{A^B problem}AB problem 。所以琪露诺打算将一个数进行拆分，来练习她学会的内容。以下会把这种拆分方式称作「纯情活泼的拆分」。 具体来说，她会把一个正整数 δdeltaδ ，拆分成若干个互不相同的大于等于2的自然数的幂次和，即： δ=p1c1+p2c2+⋯=∑picidelta=p_1^{c_1}+p_2^{c_2}+cdots =sum p_i^{c_i}δ=p1c1​​+p2c2​​+⋯=∑pici​​ 很显然地，对于一个 δdeltaδ 可能存在若干种不同的拆分方式。为此，琪露诺定义了一个「纯情」值 φδ(p1:c1,p2:c2,⋯ )varphi_delta(p_1:c_1,p_2:c_2,cdots)φδ​(p1​:c1​,p2​:c2​,⋯) ，用于衡量一种拆分的价值。有： φδ(p1:c1,p2:c2,⋯ )=c1+c2+⋯=∑civarphi_delta(p_1:c_1,p_2:c_2,cdots)=c_1+c_2+cdots =sum c_iφδ​(p1​:c1​,p2​:c2​,⋯)=c1​+c2​+⋯=∑ci​ 显然，对于每个 δdeltaδ ，存在一种拆分方式使得它的「纯情」值最大，我们将这个最大值记为 δdeltaδ 的「活泼」值，用 Φ(δ)Phi(delta)Φ(δ) 表示。特别地，如果不存在任何一种合法的拆分方式，则 Φ(δ)=9Phi(delta)=9Φ(δ)=9 。琪露诺为了验证她的拆分，找到了 nmathit nn 个数 w1,w2,⋯wnw_1,w_2,cdots w_nw1​,w2​,⋯wn​ 。你要做的就是分别求出 Φ(w1),Φ(w2),⋯Φ(wn)Phi(w_1),Phi(w_2),cdots Phi(w_n)Φ(w1​),Φ(w2​),⋯Φ(wn​) 。

标签： HBC222904[NOIP2003]侦探推理 枚举 NOIP复赛纯情活泼的拆分题解