首页 > 试题广场 >

kotori和素因子

[编程题]kotori和素因子
  • 热度指数：6496 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}kotori 拿到 n 个互不相同的正整数 a_1,a_2,\dots,a_n。她要从每个 a_i 中选出一个素因子 p_i，要求所有选出的素因子两两不同，即 p_i\neq p_j\;(i\neq j)。

\hspace{15pt}若无法满足要求输出 -1；否则输出所有选出的素因子之和 \displaystyle\sum_{i=1}^{n}p_i 的最小可能值。

输入描述:
\hspace{15pt}第一行输入整数 n\left(1\leqq n\leqq 10\right)。 
\hspace{15pt}第二行输入 n 个两两不同的整数 a_i\left(2\leqq a_i\leqq 1000\right)。


输出描述:
\hspace{15pt}若存在合法选取方案，输出最小可能和；否则输出 -1。
示例1

输入

4
12 15 28 22

输出

17

说明

可取素因子 [3,5,7,2]，和为 17；任意合法方案的和都不小于 17。
示例2

输入

5
4 5 6 7 8

输出

-1

备注:

算法知识视频讲解
添加回答
Go
草海桐头像 草海桐 
package main

/* 
    计算并存储每个数的所有素因子
    dfs遍历所有可能
 */

import (
	"fmt"
	"math"
)

// 判断一个数是否为素数
func isPrime(x int) bool {
	if x < 2 {
		return false
	}
	for i := 2; i <= int(math.Sqrt(float64(x))); i++ {
		if x%i == 0 {
			return false
		}
	}
	return true
}

// 获取一个数的所有素因子
func getPrimeFactors(x int) []int {
	factors := []int{}
	for i := 2; i <= x; i++ {
		if x%i == 0 && isPrime(i) {
			factors = append(factors, i)
			// 跳过所有i的倍数
			for x%i == 0 {
				x /= i
			}
		}
	}
	return factors
}

func main() {
	var n int
	fmt.Scanf("%d", &n)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &a[i])
	}

	// 为每个数获取所有可能的素因子
	primeFactors := make([][]int, n)
	for i, num := range a {
		primeFactors[i] = getPrimeFactors(num)
	}

	// 尝试所有可能的素因子组合，使用回溯法
	used := make([]bool, 10000) // 假设素因子不超过10000
	minSum := math.MaxInt32

	var backtrack func(index, sum int)
	backtrack = func(index, sum int) {
		if index == n {
			if sum < minSum {
				minSum = sum
			}
			return
		}

		for _, factor := range primeFactors[index] {
			if !used[factor] {
				used[factor] = true
				backtrack(index+1, sum+factor)
				used[factor] = false
			}
		}
	}

	backtrack(0, 0)

	if minSum == math.MaxInt32 {
		fmt.Println(-1)
	} else {
		fmt.Println(minSum)
	}
}

发表于 2025-09-07 22:19:42 回复(0)
牛客358919795号头像 牛客358919795号 
import math
import sys

n = int(input())
nums = list(map(int, input().split()))

def is_prime(m):
    if m < 2:
        return False
    for i in range(2, int(math.sqrt(m)) + 1):
        if m % i == 0:
            return False
    return True

# 返回 num 的所有素因子
def prime_factor(m):
    factor_list = []
    for i in range(2, int(math.sqrt(m)) + 1):
        if m % i == 0 and is_prime(i):
            factor_list.append(i)
            while m % i == 0:
                m //= i
    if m > 1 and is_prime(m):
        factor_list.append(m)
    return factor_list

# 所有素因子集合
all_factor_list = []
for num in nums:
    all_factor_list.append(prime_factor(num))

# 回溯 + 剪枝
min_sum = float('inf')
used = set()

def dfs(index, current_sum):
    global min_sum
    if current_sum >= min_sum:
        return  # 剪枝
    if index == n:
        min_sum = min(min_sum, current_sum)
        return
    for factor in sorted(all_factor_list[index]):
        if factor not in used:
            used.add(factor)
            dfs(index + 1, current_sum + factor)
            used.remove(factor)

dfs(0, 0)
if min_sum == float('inf'):
    print('-1')
else:
    print(min_sum)


发表于 2025-04-17 09:15:37 回复(0)
YSebastian0122头像 YSebastian0122
def is_prime(number):
    """
    判断一个数是否为质数
    Args:
        number: 需要判断的数字
    Returns:
        bool: 是否为质数
    """
    if number < 2:
        return False

    # 只需要检查到平方根即可
    for divisor in range(2, int(number ** 0.5) + 1):
        if number % divisor == 0:
            return False

    return True

def find_minimum_prime_factors_sum(
    current_index, used_factors, current_sum, numbers, min_sum
):
    """
    使用深度优先搜索找出每个数的一个质因子，使得这些质因子互不相同且和最小
    Args:
        current_index: 当前处理的数字索引
        used_factors: 已使用的质因子集合
        current_sum: 当前已选质因子的和
        numbers: 输入的数字列表
        min_sum: 当前找到的最小和
    Returns:
        int: 找到的最小和，如果无解则返回float('inf')
    """
    # 基础情况：所有数字都已处理完
    if current_index == len(numbers):
        return min(min_sum, current_sum)

    current_number = numbers[current_index]

    # 尝试当前数字的所有可能质因子
    for factor in range(2, current_number + 1):
        if (
            current_number % factor == 0
            and is_prime(factor)
            and factor not in used_factors
        ):

            # 选择这个质因子
            used_factors.add(factor)
            min_sum = find_minimum_prime_factors_sum(
                current_index + 1, used_factors, current_sum + factor, numbers, min_sum
            )
            # 回溯：移除这个质因子
            used_factors.remove(factor)

    return min_sum

def main():
    """
    主函数：处理输入并输出结果
    """
    # 读取输入
    n = int(input())
    numbers = list(map(int, input().split()))

    # 初始化参数
    used_factors = set()
    initial_min_sum = float("inf")

    # 执行搜索
    result = find_minimum_prime_factors_sum(
        0, used_factors, 0, numbers, initial_min_sum
    )

    # 输出结果
    if result == float("inf"):
        print(-1)
    else:
        print(result)


main()

发表于 2024-12-17 19:16:47 回复(0)
C
折耳根本根头像 折耳根本根
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define max 1001
//node存储整数和它的素因子
typedef struct{
    int data;
    int moddata[max];
    int n;
}node;
//list存储整数个数及每个整数对应的node
typedef struct{
    node *num;
    int pre;
    int numn;
}list;
list Init(int n){
    list L;
    L.numn=n;
    L.pre=0;
    L.num=(node *)malloc(sizeof(node)*n);
    return L;
}
//判断是否为素数
bool istrue(int data){
    for(int i=2;i<=data/2;i++){
        if(data%i==0) return false;
    }
    return true;
}
//每输入一个数据，向list队列中存储一个node
void Insertlist(list *L,int data){
    node temp;
    temp.data=data;
    int length=0;
    for(int i=2;i<=data;i++){
        if(data%i==0&&istrue(i)){
            temp.moddata[length++]=i;
        }
    }
    temp.n=length;
    L->num[L->pre++]=temp;
}
int path=200000000;
int temppath=0;
bool hasvisit[max];
void dfs(list *L,int depth){
    //当满足遍历到最后节点时，判断是否更新path，并返回上一层
    if(depth==L->numn){
        path=temppath<path ? temppath:path;
        return;
    }
    //对进来的那一层判断当前层队列从小到大是否含有之前没有出现的素数，有则更新temppath，进入下一层
    for(int j=0;j<L->num[depth].n;j++){
        if(!hasvisit[L->num[depth].moddata[j]]){
            hasvisit[L->num[depth].moddata[j]]=true;
            temppath+=L->num[depth].moddata[j];
            dfs(L,depth+1);
            //从下一层退回后，将原本遍历过的数退出hasvisit，并减去那部分的路径长度，继续判断当前层是否含有其他进入下一层的选择
            hasvisit[L->num[depth].moddata[j]]=false;
            temppath-=L->num[depth].moddata[j];
        }
    }
}
int main(){
    int n,a;
    scanf("%d",&n);
    list L=Init(n);
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        Insertlist(&L, a);
    }
    dfs(&L,0);
    if(path==200000000) path=-1;
    printf("%d",path);
    return 0;
}
发表于 2024-10-07 01:42:52 回复(0)
Python3
Cecilia_mm头像 Cecilia_mm 
import collections
class Solution():
    def __init__(self, alist, n):
        self.alist = alist
        self.n = n
        self.res = float('+inf')
        self.dic = collections.defaultdict(list)
        self.no_repeat_set = set()

    def is_prime(self, x):
        if x <= 1:
            return False
        for i in range(2, x):
            if x % i == 0:
                return False
        return True
    
    def dfs(self, idx, s):
        if idx == self.n:
            self.res = min(self.res, s)
            return
        for prime_factor in self.dic[self.alist[idx]]:
            if prime_factor not in self.no_repeat_set:
                self.no_repeat_set.add(prime_factor)
                self.dfs(idx+1, s+prime_factor)
                self.no_repeat_set.remove(prime_factor)
    
    def func(self):
        if self.n <= 0:
            return -1
        for ele in self.alist:
            if ele == 1:
                return -1
            for i in range(2, ele+1):
                if self.is_prime(i) and ele % i == 0:
                    self.dic[ele].append(i)
            if self.dic[ele] == []:
                return -1
        self.dfs(0, 0)
        return -1 if self.res == float('+inf') else self.res


n = int(input().strip())
alist = list(map(int, input().strip().split()))
solution = Solution(alist, n)
print(solution.func())

发表于 2024-08-31 16:45:51 回复(0)
牛客481003893号头像 牛客481003893号 
#include <bits/stdc++.h>

using namespace std;
#define int long long

int n, a[15], sushu[15], res = 0, ans = 0x3f3f3f3f, flag = 0;

//判断是不是素数
int isprime(int x) {
    for (int i = 2; i <= sqrt(x); ++i) {
        if (x % i == 0) {
            return 0;
        }
    }
    return 1;
}

void dfs(int u) {
    if (u == n) {
        ans = min(res, ans);
        flag = 1;
        return;
    }
    //先求出所有素因子
    for (int i = 2; i <= a[u]; ++i) {
        if (a[u] % i == 0 && isprime(i)) {
            //满足条件，入
            int f = 0;
            for (int j = 0; j <= u; ++j) {
                if (sushu[j] == i) {
                    f = 1;
                }
            }
            if (f == 0) {
                sushu[u] = i;
                res += i;
                dfs(u + 1);
                sushu[u] = 0;
                res -= i;
            }
        }
    }
}

signed main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    dfs(0);
    if (flag == 0) {
        cout << -1;
        return 0;
    }
    cout << ans;
    return 0;
}

发表于 2023-11-30 21:00:56 回复(0)
C++
牛客510028288号头像 牛客510028288号 
#include <climits>
#include <iostream>
#include <vector>
#include<cmath>
#include<algorithm>
#include<numeric>
using namespace std;

void dfs(int x, vector<int>& su) {
    int flag = 0;
    int a = sqrt(x);
    for (int i = 2; i <= a; i++) {
        if (!(x % i)) {
            dfs(x / i, su);
            dfs(i, su);
            flag++;
        }
    }
    if (!flag && !count(su.begin(), su.end(), x)) {
        su.push_back(x);
    }
    return;
}

void ddfs(int n, vector<vector<int>>& su, vector<int>& choose,vector<int>& val) {
    if(choose.size()==su.size()) {
        val.push_back(accumulate(choose.begin(),choose.end(),0));
        return;
    }
    for (int i = 0; i < su[n].size(); i++) {
        if (!count(choose.begin(), choose.end(), su[n][i])) {
            choose.push_back(su[n][i]);
            ddfs(n+1, su, choose, val);
            choose.pop_back();
        }
    }
    return;
}

int minadd(vector<vector<int>>& su) {
    vector<int> choose;
    vector<int> val;
    ddfs(0, su, choose, val);
    if (val.empty()) return -1;
    return *min_element(val.begin(), val.end());
}

int main() {
    int n = 0, m = 0;
    cin >> n;
    vector<vector<int>> su(n, vector<int>(0));
    for (int i = 0; i < n; i++) {
        cin >> m;
        dfs(m, su[i]);
    }
    cout << minadd(su) << endl;
    return 0;
}

发表于 2023-04-12 00:21:12 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main

import (
    "fmt"
    "math"
)

func main() {
    var n int
    fmt.Scan(&n)
    arr:=make([][]int,n)
    var x int
    for i:=0;i<n;i++{
        fmt.Scan(&x)
        tmp:=make_arr(x)
        arr[i]=tmp
    }
    // fmt.Printf("%v\n",arr)
    min:=math.MaxInt32
    vis:=map[int]bool{}
    var dfs func(int,int)
    dfs=func(j int,sum int){
        if j==n{
            if sum<min{
                min=sum
            }
            return
        }
        for i:=0;i<len(arr[j]);i++{
            x:=arr[j][i]
            if _,ok:=vis[x];ok{
                continue
            }
            sum+=x
            vis[x]=true
            dfs(j+1,sum)
            sum-=x
            delete(vis,x)
        }
    }
    dfs(0,0)
    if min==math.MaxInt32{
        fmt.Println(-1)
        return
    }
    fmt.Println(min)
}

func make_arr(x int)[]int{
    ans:=[]int{}
    for i:=2;i<=x;i++{
        if x%i==0&&check(i){
            ans=append(ans,i)
        }
    }
    return ans
}

func check(x int)bool{
    for i:=2;i<x;i++{
        if x%i==0{
            return false
        }
    }
    return true
}

发表于 2023-03-05 14:32:06 回复(0)
Java
牛客776070135号头像 牛客776070135号
import java.util.*;
public class Main {
//定义存放的list的list(因为list中数组长度可变),用来存放每个数的素因子
    static List<List<Integer>> list = new ArrayList<List<Integer>>();
    static int deepth = 0;//深度，也就是正整数的个数；
    static int minRes = 10000;//返回的结果
    static int[] vis = new int[1000];//因为每个访问的数都不重复，所以vis[i]指i是否被访问过
    static int sum = 0;//搜索时的和
    static boolean flag = false; //flag为1说明已经找到了最小值（遍历到了最底层（说明每个数都有素因子，只要有一个数没有，则无法递归到最底层））
//先找到每个数的素因子，然后再深度搜索满足条件的最小值，若不存在，则输出-1
//判断是否为素数
    public static boolean isSu(int n) {
        if (n == 1) {
            return false;
        }
        //从2开始到根号n之间，只要找到n可以除尽的数，说明n有其他因子，则n不是素数
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

//找素因子,n为输入的数，x为在list中存放的位置(第几行)
    public static void prime(int n, int x) {
        List<Integer> tempList = new ArrayList<Integer>();
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                if (isSu(i)) {
                    tempList.add(i); //满足素数，则存入
                }
                //还要存对应的另外一个因子（因为只遍历到根号n），前提是另外一个因子和此因子不相等，且也为素数
                if (i * i != n && isSu(n / i)) {
                    tempList.add(n / i);
                }
            }
        }
        list.add(tempList);
    }

//深度搜索:y为第几层
    public static void dfs(int y) {
        if (y == deepth) { //如果遍历深度到最底层，退出，只能往回找了
            flag = true;//此时说明每一层都有素因子，合法的，一定会有最小值
            minRes = Math.min(minRes, sum);
            return;
        }
        for (int i = 0; i < list.get(y).size(); i++) {
            if (vis[list.get(y).get(i)] == 0) { //说明没有被访问
                sum += list.get(y).get(i);
                vis[list.get(y).get(i)] = 1;//标记为已访问
                dfs(y + 1);//开始遍历下一层;
                vis[list.get(y).get(i)] = 0;//遍历后回溯要先将该点标记为未访问
                sum -= list.get(y).get(i);//标为未读后要将该点的值去掉
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        deepth = Integer.parseInt(in.nextLine());
        String[] res = in.nextLine().split(" ");
        //获取每一个数的素因子，放入list中
        for (int i = 0; i < deepth; i++) {
            prime(Integer.parseInt(res[i]), i);
        }
        //开始从第一层深度搜索
        dfs(0);
        //输出结果
        if (!flag) {
            System.out.println("-1");
        } else {
            System.out.println(minRes);
        }
    }
}
发表于 2022-04-16 21:33:02 回复(0)
提交观点

问题信息

数论 数学
来自：华为机试编程模拟题7
难度：
9条回答 3048浏览

热门推荐

通过挑战的用户

查看代码

相关试题

kotori和素因子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号