首页 > 试题广场 >

kotori和素因子

[编程题]kotori和素因子
  • 热度指数：6182 时间限制：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

备注:

算法知识视频讲解
添加回答
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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

kotori和素因子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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