元素分裂第三题,通过率60 let n = read_line() - 0; let nums = read_line().split(" ").map((item) => parseInt(item)); nums.sort((a,b) => a-b); let max = Math.max(...nums); let dp = new Array(Math.pow(10,5)).fill(Math.pow(10,6)); dp[0] = -1; dp[1] = 0; dp[2] = 1; dp[3] = 2; dp[4] = 3; for (let i = 5;i <= max;i++) { let arr = getYinZi(i); for (let j = 1;j < arr.length - 1;j++) { dp[i] = Math.min(dp[i],1 + dp[arr[j]] + dp[i / arr[j]]); } dp[i] = Math.min(dp[i] ,dp[i - 1] + 1); } let res = 0; for (let item of nums) { res += dp[item]; } console.log(res); function getYinZi(num) { let res = new Set(); for (let i = 1;i * i <= num;i++) { if(num % i == 0) { res.add(i); res.add(num / i); } } let arr = Array.from(res); arr.sort((a,b) => a-b); return arr; }