#MXCSPJ0102. MXCSP-J第一套模拟卷T2 拆分数字(split)

MXCSP-J第一套模拟卷T2 拆分数字(split)

T2 拆分数字(split)

容易发现,对于所有 nn 都一定能表示(指用 m1,m2,...m_1,m_2,...),不过不一定是 kk 个数。那我们可以求出最少和最多用多少个数表示,再看看能否累加或减少到 kk 个。

首先最多一定是 n=30×nn = 3^0 \times n,最少则是 nn 在三进制下的非零数的个数,不妨设其为 mm。如果 m>km > k,一定无解,m=km = k 有解。m<km < k 则需要尝试拆分调整。

观察到我们可以进行这样的拆分:3i=3i1+3i1+3i13^i = 3^{i-1} + 3^{i-1} + 3^{i-1},即进行这样的一次拆分可以使原本的 mm 增加 22。而 nkn \ge k,所有 mm 一直拆分下去,一定有一个时刻 k\ge k。只需要判断 m,km,k 的奇偶性是否相同即可。