题解：P15802 [GESP202603 七级] 拆分

· · 题解

解题思路

尽可能分解为 3 和 2 为最优。

证明如下：

  1. 最优分解中一定不含有 a_i \geq 5 的数字：
    • 假设 a_i \geq 5，那么我们可以将 a_i 拆分为 2 和 a_i - 2，2 \times (a_i -2) = 2\times a_i - 4，令 2 \times a_i - 4 \geq a_i，即 a_i \geq 4。
    • 即当 a_i > 4 时，将 a_i 拆分为 2 和 a_i - 2，更优。
  2. 最有分解中一定不含有 a_i = 1（n \neq 1）：
    • 若 a_i 为 1，那么当 n\neq 1 时必然存在 x + 1 > 1 \times x，即将 1 加到别的数上一定更优。
  3. 最优解中可能含有 4：
  4. 确定 2 和 3 的个数：
    • 求 a, b 满足 2 \times a + 3 \times b = n，2^a\times 3^b 的最大值。
    • 根据 n 除以 3 的余数分类：

我们可以使用快速幂算法或者是预处理 3^k 数组解决。

AC_Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10, MOD = 1e9;

int fact3[N];
int fact2[3];

int main()
{
    fact3[0] = 1;
    for (int i = 1; i < N; ++ i )
        fact3[i] = (LL)fact3[i - 1] * 3 % MOD;

    fact2[0] = 1, fact2[1] = 2, fact2[2] = 4;

    int T;
    cin >> T;

    while (T -- )
    {
        int x;
        cin >> x;

        if (x == 1)
        {
            cout << 1 << '\n';
            continue;
        }

        int c3 = x / 3, c2 = 0;

        if (x % 3 == 2)
            c2 ++ ;
        else if (x % 3 == 1)
            c3 --, c2 = 2 ;

        cout << (LL)fact3[c3] * fact2[c2] % MOD << '\n';
    }

    return 0;
}