首页 > 试题广场 >

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

备注:

算法知识视频讲解
开通博客
头像 牛客439623629号
发表于 2022-08-19 21:58:27
递归 #include <bits/stdc++.h> using namespace std; int n; int a[1010];//正整数的值 int mi=1e9; //判断是否为质数 bool pri 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 牛客342264138号
发表于 2022-07-05 09:45:54
operation = input() #操作次数 items = input() #输入序列 #将输入序列转换成列表 items_str = items.split(' ') items_list  展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 牛客338107602号
发表于 2022-07-04 12:25:32
总结：1.在计算素数时，除数只需要计算到Math.sqrt(n)，不需要遍历到n.而且虽然1不是素因子，但n/1可能是素因子，这种情况应该考虑在内。2.当将每个整数的因子统计好后，可以使用深度优先搜索，逐层寻找素因子，也可以使用数组统计已被访问过的因子。 import java.util.*; pu 展开全文
去ta的博客 赞 (3) 回复(4) 收起
头像 酸甜苦辣复何求
发表于 2022-12-14 15:16:00
// 思路：将每个数都取出一个不同的因子，依次相加，在对比选出最小的， // 例如第一个数有a, b因子，第二个数有a，c,d因子，那么对比a+c,a+d,b+a,b+c,b+d,得到最小的。 #include <stdio.h> #include <math.h> #in 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 zzfyupup
发表于 2022-10-18 17:44:54
/* kotori拿到了一些正整数。她决定从每个正整数取出一个素因子。但是，kotori有强迫症，她不允许两个不同的正整数取出相同的素因子。 她想知道，最终所有取出的数的和的最小值是多少？ 注：若 a\bmod k== 0amodk==0，则称 kk 是 aa 的因子。若一个数有且仅有两个因子， 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 牛客229776976号
发表于 2022-06-24 20:54:37
n=input() s=list(map(int,input().split())) suyinzilist=[] path=[] tmp=[]   def sushu(k):  #判断是否为素数     for i in range(2,int(k 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 drawer
发表于 2025-11-27 19:28:21
遍历一遍所有非重复的质因子即可； prime[i] == 0 && nn % i == 0&&find(de.begin(),de.end(),i)==de.end() void dfs(int index) { if (index == n) { 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 什么又被限制
发表于 2022-10-08 09:58:14
#include <iostream> #include <algorithm> #include <cmath> #include <vector> using namespace std; const int maxn = 1e3 + 5; c 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 捞我吧求求乐
发表于 2023-08-09 10:54:26
题干要求计算素因子的和，n个数，每个数都可能有若干个素因子，选择当前数的素因子相当于一次分叉，那么选择过程形成一个多叉树，最后一个数的素因子选择后，相当于到达多叉树的叶子，此时计算所有素因子的和。想要遍历所有可能的和，就需要使用深度优先遍历dfs的方法遍历整个多叉树，最后能得出最小的和。 #incl 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Coming680
发表于 2022-03-19 15:46:54
#include<iostream> #include<vector> #include<map> #include<queue> #include<set> #define INF 1e+7 using namespace std; ve 展开全文
去ta的博客 赞 (1) 回复(2) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

kotori和素因子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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