G7019 [GESP202603 七级] 拆分 题解

知识点：数学贪心、快速幂、整数拆分。

解题思路

最大化拆分后乘积时尽量使用3：余0全取3，余1改成一个4，余2保留一个2；模10^9用快速幂。

为什么正确

任何大于4的部分可拆出3提高乘积，1不应保留，两个3比三个2更优，因此最优只需3及一个2或4。

易错点

本题允许不再拆分，n≤4直接输出n；余1不能保留3+1，应改成2+2。

复杂度

每组时间O(log n)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    auto pw=[](long long a,int b) {
        long long v=1;
        while(b) {
            if(b&1)v=v*a%1000000000;
            a=a*a%1000000000;
            b>>=1;
        }
        return v;
    }
    ;
    while(t--) {
        int n;
        cin>>n;
        long long ans;
        if(n<=4)ans=n;
        else if(n%3==0)ans=pw(3,n/3);
        else if(n%3==1)ans=pw(3,n/3-1)*4%1000000000;
        else ans=pw(3,n/3)*2%1000000000;
        cout<<ans<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。