因数分解 (11294767)

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

题意

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

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

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

输出最大优秀因子数量，对 取模。

分析

设 ，其中 为不同的素数，，。

一个"优秀因子"必须能被所有 整除，即形如 ，其中 。

因此优秀因子的数量为：

$$

问题转化：将 分拆为若干正整数之和（，），最大化这些正整数的乘积。

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

• 不用 1（乘以 1 无贡献）
• 若某个分量 ，可以拆分：，说明可以继续分
• 不用大于 4 的分量，尽量用 3

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

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

规律（）：

• ：答案为
• ：答案为 （拿出 4=2×2，其余用 3）
• ：答案为

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

验证样例：，，答案 ✓（对应 ，分拆为 ）

复杂度

• 时间复杂度：（快速幂）
• 空间复杂度：

代码

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);
    }
}