HJ154 kotori和素因子

题目题解(43)讨论(12)排行中等 通过率43.74% 时间限制1秒 空间限制256M知识点数论数学校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述kotori 拿到 nn 个互不相同的正整数 a1,a2,…,ana1​,a2​,…,an​。她要从每个 aiai​ 中选出一个素因子pipi​要求所有选出的素因子两两不同即 pi≠pj (i≠j)pi​​pj​(i​j)。若无法满足要求输出 −1−1否则输出所有选出的素因子之和 ∑i1npii1∑n​pi​ 的最小可能值。输入描述第一行输入整数 n(1≦n≦10)n(1≦n≦10)。第二行输入 nn 个两两不同的整数 ai(2≦ai≦1000)ai​(2≦ai​≦1000)。输出描述若存在合法选取方案输出最小可能和否则输出 −1−1。示例1输入4 12 15 28 22复制输出17复制说明可取素因子 [3,5,7,2][3,5,7,2]和为 1717任意合法方案的和都不小于 1717。示例2输入5 4 5 6 7 8复制输出-1#include bits/stdc.h using namespace std; int n; int a[1010];//正整数的值 int mi1e9; //判断是否为质数 bool primer(int x){ for(int i2;i*ix;i){ if(x%i0){ return false; } } return true; } void dfs(int x,setint s,int temp){ if(xn){ mimin(mi,temp); return; } for(int i2;ia[x];i){ if(a[x]%i0 primer(i)!s.count(i)){ s.insert(i); dfs(x1,s,tempi); s.erase(i); } } } int main(){ cinn; for(int i0;in;i){ cina[i]; } setint s; dfs(0,s,0); if(mi1e9)cout-1; else coutmi; return 0; }