3669. K 因数分解

题目描述

给你两个整数 n 和 k，将数字 n 恰好分割成 k 个正整数，使得这些整数的乘积等于 n。

返回一个分割方案，使得这些数字中 最大值 和 最小值 之间的差值最小化。结果可以以 任意顺序 返回。

示例 1：

输入：n = 100, k = 2

输出：[10,10]

解释：

分割方案 [10, 10] 的结果是 10 * 10 = 100，且最大值与最小值的差值为 0，这是最小可能值。

示例 2：

输入：n = 44, k = 3

输出：[2,2,11]

解释：

分割方案 [1, 1, 44] 的差值为 43
分割方案 [1, 2, 22] 的差值为 21
分割方案 [1, 4, 11] 的差值为 10
分割方案 [2, 2, 11] 的差值为 9

因此，[2, 2, 11] 是最优分割方案，其差值最小，为 9。

提示：

4 <= n <= 10⁵
2 <= k <= 5
k 严格小于 n 的正因数的总数。

解法

方法一

Python3JavaC++GoTypeScript

mx = 10**5 + 1
g = [[] for _ in range(mx)]
for i in range(1, mx):
    for j in range(i, mx, i):
        g[j].append(i)


class Solution:
    def minDifference(self, n: int, k: int) -> List[int]:
        def dfs(i: int, x: int, mi: int, mx: int):
            if i == 0:
                nonlocal cur, ans
                d = max(mx, x) - min(mi, x)
                if d < cur:
                    cur = d
                    path[i] = x
                    ans = path[:]
                return
            for y in g[x]:
                path[i] = y
                dfs(i - 1, x // y, min(mi, y), max(mx, y))

        ans = None
        path = [0] * k
        cur = inf
        dfs(k - 1, n, inf, 0)
        return ans

class Solution {
    static final int MX = 100_001;
    static List<Integer>[] g = new ArrayList[MX];

    static {
        for (int i = 0; i < MX; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 1; i < MX; i++) {
            for (int j = i; j < MX; j += i) {
                g[j].add(i);
            }
        }
    }

    private int cur;
    private int[] ans;
    private int[] path;

    public int[] minDifference(int n, int k) {
        cur = Integer.MAX_VALUE;
        ans = null;
        path = new int[k];
        dfs(k - 1, n, Integer.MAX_VALUE, 0);
        return ans;
    }

    private void dfs(int i, int x, int mi, int mx) {
        if (i == 0) {
            int d = Math.max(mx, x) - Math.min(mi, x);
            if (d < cur) {
                cur = d;
                path[i] = x;
                ans = path.clone();
            }
            return;
        }
        for (int y : g[x]) {
            path[i] = y;
            dfs(i - 1, x / y, Math.min(mi, y), Math.max(mx, y));
        }
    }
}

class Solution {
public:
    static const int MX = 100001;
    static vector<vector<int>> g;

    vector<int> ans;
    vector<int> path;
    int cur;

    vector<int> minDifference(int n, int k) {
        if (g.empty()) {
            g.resize(MX);
            for (int i = 1; i < MX; i++) {
                for (int j = i; j < MX; j += i) {
                    g[j].push_back(i);
                }
            }
        }

        cur = INT_MAX;
        ans.clear();
        path.assign(k, 0);

        dfs(k - 1, n, INT_MAX, 0);
        return ans;
    }

private:
    void dfs(int i, int x, int mi, int mx) {
        if (i == 0) {
            int d = max(mx, x) - min(mi, x);
            if (d < cur) {
                cur = d;
                path[i] = x;
                ans = path;
            }
            return;
        }
        for (int y : g[x]) {
            path[i] = y;
            dfs(i - 1, x / y, min(mi, y), max(mx, y));
        }
    }
};

vector<vector<int>> Solution::g;

const MX = 100001

var g [][]int

func init() {
    g = make([][]int, MX)
    for i := 1; i < MX; i++ {
        for j := i; j < MX; j += i {
            g[j] = append(g[j], i)
        }
    }
}

var (
    cur  int
    ans  []int
    path []int
)

func minDifference(n int, k int) []int {
    cur = math.MaxInt32
    ans = nil
    path = make([]int, k)
    dfs(k-1, n, math.MaxInt32, 0)
    return ans
}

func dfs(i, x, mi, mx int) {
    if i == 0 {
        d := max(mx, x) - min(mi, x)
        if d < cur {
            cur = d
            path[i] = x
            ans = slices.Clone(path)
        }
        return
    }
    for _, y := range g[x] {
        path[i] = y
        dfs(i-1, x/y, min(mi, y), max(mx, y))
    }
}

const MX = 100001;
const g: number[][] = Array.from({ length: MX }, () => []);
for (let i = 1; i < MX; i++) {
    for (let j = i; j < MX; j += i) {
        g[j].push(i);
    }
}

function minDifference(n: number, k: number): number[] {
    let cur = Number.MAX_SAFE_INTEGER;
    let ans: number[] | null = null;
    const path: number[] = Array(k).fill(0);

    function dfs(i: number, x: number, mi: number, mx: number): void {
        if (i === 0) {
            const d = Math.max(mx, x) - Math.min(mi, x);
            if (d < cur) {
                cur = d;
                path[i] = x;
                ans = [...path];
            }
            return;
        }
        for (const y of g[x]) {
            path[i] = y;
            dfs(i - 1, Math.floor(x / y), Math.min(mi, y), Math.max(mx, y));
        }
    }

    dfs(k - 1, n, Number.MAX_SAFE_INTEGER, 0);
    return ans ?? [];
}

3669. K 因数分解

题目描述

解法

方法一

评论