题目描述
$kotori$ 拿到了一些正整数。她决定从每个正整数取出一个素因子。但是,$kotori$有强迫症,她不允许两个不同的正整数取出相同的素因子。
她想知道,最终所有取出的数的和的最小值是多少?
注:若 $a$ $mod$ $k$ $==$ $0$,则称 $k$ 是 $a$ 的因子。若一个数有且仅有两个因子,则称其是素数。显然 $1$ 只有一个因子,不是素数。
输入描述
第一行一个正整数 $n$,代表 $kotori$ 拿到正整数的个数。
第二行共有 $n$ 个数 ,表示每个正整数的值。
保证不存在两个相等的正整数。
$1$ $\leq$ $n$ $\leq$ $10$
$2$ $\leq$ $a_{i}$ $\leq$ $100$
输出描述
一个正整数,代表取出的素因子之和的最小值。若不存在合法的取法,则输出 $-1$。
样例输入
4
12 15 28 22
样例输出
17
质数 + dfs
由于只能从每个数的素因子中选出一个且互不相同的序列,由于数组大小最大为 $10$,其中$2$ - $1000$内素因子最多为 $4$,分别是最小的 $210$($2$,$3$,$5$,$7$),最大的 $990$($2$,$3$,$5$,$11$)。
-
定义 $dfs (u,sum)$
-
$u$:当前遍历到第几个数组,$sum$:当前的素因子序列之和
-
递归起点:$dfs(0, 0)$,递归终点:$u$ = $n$
爆搜每一种情况,如果答案没更新,则返回 $-1$
附C++,Java,Python3,JavaScript,Go代码
C++代码:(运行时间:2 ms,运行空间:384 KB)
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int N = 20, M = 1010;
int a[N];
bool st[M];
vector<int> g[N];
set<int> s;
int n, res = 1e9;
bool is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++) {
if (x % i == 0) return false;
}
return true;
}
void dfs(int u, int sum) {
if (u == n) {
res = min(res, sum);
return;
}
for (auto x : g[u]) {
if (s.find(x) == s.end()) {
s.insert(x);
dfs(u + 1, sum + x);
s.erase(x);
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
for (int i = 2; i <= M; i ++) {
if (is_prime(i)) st[i] = true;
else st[i] = false;
}
for (int i = 0; i < n; i ++) {
for (int j = 2; j <= a[i]; j ++) {
if (st[j] && a[i] % j == 0) g[i].push_back(j);
}
}
dfs(0, 0);
if (res == 1e9) cout << -1;
else cout << res;
return 0;
}
Java代码:(运行时间:166 ms,运行空间:16908 KB)
import java.util.*;
import java.io.*;
public class Main {
static final int N = 20, M = 1010;
//static Map<Integer, Integer> map = new HashMap<>();
static Set<Integer> set = new HashSet<>();
static List<Integer>[] g;
static boolean[] st = new boolean[M];
static int[] a;
static int n, res = (int)1e9;
static boolean is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++) {
if (x % i == 0) return false;
}
return true;
}
static void dfs(int u, int sum) {
if (u == n) {
res = Math.min(res, sum);
return;
}
for (int i = 0; i < g[u].size(); i ++) {
// HashMap写法
/*if (!map.containsKey(g[u].get(i))) {
map.put(g[u].get(i), 1);
dfs(u + 1, sum + g[u].get(i));
map.remove(g[u].get(i));
}*/
// HashSet写法
if (!set.contains(g[u].get(i))) {
set.add(g[u].get(i));
dfs(u + 1, sum + g[u].get(i));
set.remove(g[u].get(i));
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
g = new ArrayList[n];
Arrays.setAll(g, l -> new ArrayList<>());
a = new int[n];
for (int i = 0; i < n; i ++) a[i] = sc.nextInt();
Arrays.sort(a);
for (int i = 2; i < M; i ++) {
if (is_prime(i)) st[i] = true;
else st[i] = false;
}
for (int i = 0; i < n; i ++) {
for (int j = 2; j <= a[i]; j ++) {
if (st[j] && a[i] % j == 0)
g[i].add(j);
}
}
dfs(0, 0);
if (res == 1e9) System.out.println(-1);
else System.out.println(res);
}
}
Python3代码:(运行时间:57 ms,运行空间:4688 KB)
is_prime = lambda x: False if any(x % k == 0 for k in range(2, x)) else x != 1
def dfs(u: int, sum: int):
if u == n:
global res
res = min(res, sum)
return
for _, x in enumerate(g[u]):
if x not in s:
s.add(x)
dfs(u + 1, sum + x)
s.remove(x)
res, M = 1e9, 1010
n = int(input())
a = list(map(int, input().split()))
s = set()
st = [True if is_prime(i) else False for i in range(M)]
g = [[j for j in range(2, x + 1) if st[j] and x % j == 0] for x in a]
dfs(0, 0)
print(-1 if res == 1e9 else res)
JavaScript代码:(运行时间:88 ms,运行空间:14900 KB)
const readline = require('readline')
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
})
const lines = []
rl.on('line', (input) => {
lines.push(input);
})
rl.on('close', () => {
let l = 0;
let t = 1;
const output = [];
for (let i = 0; i < t; i++) {
const [n] = lines[l ++].trim().split(' ').map(Number);
const a = lines[l ++].trim().split(' ').map(Number);
output[i] = solve(n, a);
}
console.log(output.join(''));
});
const M = 1010;
let res = 1e9;
function is_prime(x) {
if (x < 2) return false;
for (let i = 2; i <= x / i; i ++) {
if (x % i == 0) return false;
}
return true;
}
function dfs(u, sum, g, set) {
if (u === g.length) {
res = Math.min(res, sum);
return;
}
for (let i = 0; i < g[u].length; i++) {
if (!set.has(g[u][i])) {
set.add(g[u][i]);
dfs(u + 1, sum + g[u][i], g, set);
set.delete(g[u][i]);
}
}
}
function solve(n, a) {
const g = new Array(n).fill(null).map(() => []);
const st = new Array(M);
const set = new Set();
for (let i = 2; i < M; i++) {
if (is_prime(i)) st[i] = true;
else st[i] = false;
}
for (let i = 0; i < n; i++) {
for (let j = 2; j <= a[i]; j++) {
if (st[j] && a[i] % j === 0)
g[i].push(j);
}
}
dfs(0, 0, g, set);
return res == 1e9 ? -1 : res;
}
Go代码:(运行时间:3 ms,运行空间:904 KB)
package main
import (
. "fmt"
)
const (
N int = 20
M int = 1010
)
var (
a = make([] int, N)
st = make([] bool, M)
g = make([][] int, N)
ma = map[int]int{}
n int
res int = 1e9
)
func is_prime(x int) bool {
if (x < 2) {
return false;
}
for i := 2; i <= x / i; i ++ {
if x % i == 0 {
return false;
}
}
return true;
}
func dfs(u, sum int) {
if u == n {
res = min(res, sum)
return
}
for _, x := range g[u] {
if ma[x] == 0 {
ma[x] = 1
dfs(u + 1, sum + x)
ma[x] = 0
}
}
}
func main() {
Scan(&n)
for i := 0; i < n; i ++ {
Scan(&a[i])
}
for i := 2; i < M; i ++ {
if is_prime(i) {
st[i] = true
} else {
st[i] = false
}
}
for i := 0; i < n; i ++ {
for j := 2; j <= a[i]; j ++ {
if st[j] && a[i] % j == 0 {
g[i] = append(g[i], j)
}
}
}
dfs(0, 0)
if res == 1e9 {
Println(-1)
} else {
Println(res)
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}