当前位置:网站首页>AcWing 2456. 记事本
AcWing 2456. 记事本
2022-07-06 08:59:00 【Easenyang】
题目描述
最初在一个记事本上只有一个字符 A。
你每次可以对这个记事本进行两种操作:
Copy All (复制全部) :
你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) :
你可以粘贴你上一次复制的字符。 给定一个数字 n。
你需要使用最少的操作次数,在记事本中打印出恰好 n 个 A。
输出能够打印出 n 个 A 的最少操作次数。
输入格式
一个整数 n。
输出格式
一个整数,表示最少操作次数。
数据范围
1 ≤ n ≤ 1 0 6 1≤n≤10^6 1≤n≤106
题目链接:记事本
思路:
我们先考虑输入的数为质数 n 的情况:质数肯定是必须要先复制 1 次,然后粘贴 n - 1次。(例如 7 只能是复制 1 次,粘贴 6 次得到,大家可以在草稿本上推一次)
那么对于合数的情况,我们就可以去分解质因数,然后不断粘贴得到。
举个例子:
24 = 22 * 32。我们先去复制粘贴得到2,复制 1 次,粘贴 2 - 1次,得到 22 就又要复制 1 次,粘贴 2-1次,然后把22当成整体,复制 1 次,粘贴 3-1次,再复制 1 次,粘贴 2-1 次。共2x2+3x2 = 10次
代码:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int n = new Scanner(System.in).nextInt();
int res = 0;;
for (int i = 2; i <= n; i++) {
int s = 0; //看当前质因数用到了几次
while (n % i == 0) {
s++;
n /= i;
}
if (s > 0) {
res += i * s;
}
}
System.out.println(res);
}
}
边栏推荐
- Advanced Computer Network Review(5)——COPE
- Selenium+pytest automated test framework practice
- [oc]- < getting started with UI> -- learning common controls
- 数字人主播618手语带货,便捷2780万名听障人士
- LeetCode:162. Looking for peak
- UnsupportedOperationException异常
- Intel distiller Toolkit - Quantitative implementation 3
- vb. Net changes with the window, scales the size of the control and maintains its relative position
- Simclr: comparative learning in NLP
- Mise en œuvre de la quantification post - formation du bminf
猜你喜欢
CUDA implementation of self defined convolution attention operator
[OC]-<UI入门>--常用控件-UIButton
LeetCode:221. 最大正方形
LeetCode:124. 二叉树中的最大路径和
UML diagram memory skills
Advanced Computer Network Review(5)——COPE
Advanced Computer Network Review(3)——BBR
SAP ui5 date type sap ui. model. type. Analysis of the parsing format of date
不同的数据驱动代码执行相同的测试场景
一篇文章带你了解-selenium工作原理详解
随机推荐
超高效!Swagger-Yapi的秘密
不同的数据驱动代码执行相同的测试场景
[OC foundation framework] - [set array]
CUDA implementation of self defined convolution attention operator
MYSQL卸载方法与安装方法
Using C language to complete a simple calculator (function pointer array and callback function)
【嵌入式】使用JLINK RTT打印log
Leetcode: Jianzhi offer 04 Search in two-dimensional array
Target detection - pytorch uses mobilenet series (V1, V2, V3) to build yolov4 target detection platform
Tdengine biweekly selection of community issues | phase III
Compétences en mémoire des graphiques UML
Intel distiller Toolkit - Quantitative implementation 3
Current situation and trend of character animation
[oc]- < getting started with UI> -- common controls - prompt dialog box and wait for the prompt (circle)
一改测试步骤代码就全写 为什么不试试用 Yaml实现数据驱动?
[OC]-<UI入门>--常用控件的学习
TDengine 社区问题双周精选 | 第三期
多元聚类分析
LeetCode:39. 组合总和
KDD 2022 paper collection (under continuous update)