5716. 好因子的最大数目

算法

找规律 + 数学

• 数据范围很大，无法在线性时间内求解
• 经过找规律发现，如果将 primeFactors 个质数分为若干个 p_i，每个 p_i 出现的次数为 c_i，那么必须满足 $sum_{i} c_i = p$，使用这种方案，好因子的数目为 $\prod_{i} c_i$
  • 因为好因子中，每个因子 p_i 至少选一个，至多全选，选法总数就是 $\prod_{i} c_i$
• 因此，最终的答案和选的质数没有关系，只和每种质数的个数有关，这道题就转化为了 LeetCode 343. 整数拆分
• 等价于在 $sum_{i} c_i = p$ 的条件下最大化 $\prod_{i} c_i$
• 因此，能选 3 就尽量选 3，不行就选 2，不能有 1

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;

int qpow(int a, int b, int p = P) {
    int ans = 1 % p;
    while (b) {
        if (b & 1) ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return ans;
}

class Solution {
   public:
    int maxNiceDivisors(int p) {
        if (p == 1) return 1;
        if (p == 2) return 2;
        int q = p / 3, r = p % 3;
        if (r == 0)
            return qpow(3, q);
        else if (r == 1)
            return qpow(3, q - 1) * 4ll % P;
        else
            return qpow(3, q) * 2ll % P;
    }
};

时间复杂度

• 直接计算：O(1)