因数分解 (11294767)

题目链接: https://www.nowcoder.com/practice/ecfcba5a9da14f5d82c79ca5727a4113

题意

给定正整数 $n$ ，构造一个数 $m$ ，满足：

$m$ 的质因数个数（含重复）恰好为 $n$ ，且这些质因子之积等于 $m$
最大化 $m$ 的"优秀因子"数量

优秀因子定义：若 $m$ 的某个因子能被 $m$ 的每一个质因子整除，则称为优秀因子。

输出最大优秀因子数量，对 $10^9+7$ 取模。

分析

设 $m = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$ ，其中 $p_i$ 为不同的素数， $a_1 + a_2 + \cdots + a_k = n$ ， $a_i \geq 1$ 。

一个"优秀因子"必须能被所有 $p_i$ 整除，即形如 $p_1^{b_1} \times p_2^{b_2} \times \cdots \times p_k^{b_k}$ ，其中 $1 \leq b_i \leq a_i$ 。

因此优秀因子的数量为：

$ $a_1 \times a_2 \times \cdots \times a_k$ $

问题转化：将 $n$ 分拆为若干正整数之和（ $a_1 + \cdots + a_k = n$ ， $a_i \geq 1$ ），最大化这些正整数的乘积。

这是经典的"整数分拆最大化乘积"问题：

不用 1（乘以 1 无贡献）
若某个分量 $\geq 5$ ，可以拆分： $a \geq 5 \Rightarrow 2(a-2) = 2a-4 > a$ ，说明可以继续分
不用大于 4 的分量，尽量用 3

- $3+3 > 2+2+2$ （9 > 8），所以 3 比 2 更优

- $3+1 < 2+2$ （3 < 4），所以遇到余 1 时，用两个 2 替代一个 3 加一个 1

规律（ $n \geq 2$ ）：

$n \bmod 3 = 0$ ：答案为 $3^{n/3}$
$n \bmod 3 = 1$ ：答案为 $4 \times 3^{(n-4)/3}$ （拿出 4=2×2，其余用 3）
$n \bmod 3 = 2$ ：答案为 $2 \times 3^{(n-2)/3}$

特殊情况： $n = 1$ 时答案为 $1$ （只有 $m$ 本身一个因子）。

验证样例： $n = 5$ ， $5 = 3 + 2$ ，答案 $= 3 \times 2 = 6$ ✓（对应 $m = 200 = 2^3 \times 5^2$ ，分拆为 $a_1=3, a_2=2$ ）

复杂度

时间复杂度： $O(\log n)$ （快速幂）
空间复杂度： $O(1)$

代码

C++

#include<bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        long long ans;
        if (n == 1) ans = 1;
        else if (n == 2) ans = 2;
        else if (n % 3 == 0) ans = power(3, n/3, MOD);
        else if (n % 3 == 1) ans = 4 * power(3, (n-4)/3, MOD) % MOD;
        else ans = 2 * power(3, (n-2)/3, MOD) % MOD;
        cout << ans << "\n";
    }
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static final long MOD = 1_000_000_007L;

    static long power(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            long n = Long.parseLong(br.readLine().trim());
            long ans;
            if (n == 1) ans = 1;
            else if (n == 2) ans = 2;
            else if (n % 3 == 0) ans = power(3, n/3, MOD);
            else if (n % 3 == 1) ans = 4 * power(3, (n-4)/3, MOD) % MOD;
            else ans = 2 * power(3, (n-2)/3, MOD) % MOD;
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}