题目链接: 2507. 使用质因数之和替换后可以取到的最小值 - 力扣(Leetcode)
题面
给你一个正整数 n
。
请你将 n
的值替换为 n
的 质因数 之和,重复这一过程。
- 注意,如果
n
能够被某个质因数多次整除,则在求和时,应当包含这个质因数同样次数。
返回 n
可以取到的最小值。
示例 1:
输入:n = 15
输出:5
解释:最开始,n = 15 。
15 = 3 * 5 ,所以 n 替换为 3 + 5 = 8 。
8 = 2 * 2 * 2 ,所以 n 替换为 2 + 2 + 2 = 6 。
6 = 2 * 3 ,所以 n 替换为 2 + 3 = 5 。
5 是 n 可以取到的最小值。
示例 2:
输入:n = 3
输出:3
解释:最开始,n = 3 。
3 是 n 可以取到的最小值。
提示:
2 <= n <= 1e5
解题思路
一个数一定可以被分解为一个或者多个质数,这些质数被称为这个数的质因数,所以要解决这个题的问题就化解为求一个树的质因数了,因此我们想到:因为本题的数据量不大,仅有 1e5
,我们可以把所有的质数都求出来,再利用求出的表计算所有的质因数。但是事实上,因为这种方法求出了很多可能根本不会使用到的值,浪费了时间,因此我们可以进行一下优化。
ACCode
class Solution {
public:
int divide(int n) {
int ans = 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
int k = 0;
while (n % i == 0) {
n /= i;
k++;
}
ans += (i * k); // 拥有 k 个等于 i 的质因子
}
}
if (n > 1) {
ans += n;
}
return ans;
}
int smallestValue(int n) {
int x = divide(n);
while (x != n) {
n = x;
x = divide(n);
}
return x;
}
};
作者:NorthCity1984
出处:https://grimoire.cn/acm/chicken-number.html
版权:本文《【leetcode】只(质)因树之和》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任
出处:https://grimoire.cn/acm/chicken-number.html
版权:本文《【leetcode】只(质)因树之和》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任
还能说话吗😀
四个月不发博客了是吧,什么懒✓
黄昏见证虔诚的信徒!!只因门永存!gin门!!!
只因。。。。 鸡你太美