当前位置:网站首页>AcWing 2456. Notepad
AcWing 2456. Notepad
2022-07-06 09:10:00 【Easenyang】
Title Description
Initially, there was only one character on a notepad A.
You can do two things with this notebook at a time :
Copy All ( Copy all ) :
You can copy all the characters in this Notepad ( Partial duplication is not allowed ).
Paste ( Paste ) :
You can paste the last character you copied . Given a number n.
You need to use the least number of operations , Print out exactly... In Notepad n individual A.
The output can print out n individual A The minimum number of operations .
Input format
An integer n.
Output format
An integer , Indicates the minimum number of operations .
Data range
1 ≤ n ≤ 1 0 6 1≤n≤10^6 1≤n≤106
Topic link : Notepad
Ideas :
Let's first consider that the input number is a prime number n The situation of : Prime numbers must be copied first 1 Time , Then paste n - 1 Time .( for example 7 Only copy 1 Time , Paste 6 Time to get , You can push it once on the draft book )
So for the case of composite numbers , We can decompose the prime factor , Then keep pasting to get .
for instance :
24 = 22 * 32. Let's copy and paste to get 2, Copy 1 Time , Paste 2 - 1 Time , obtain 22 You have to copy again 1 Time , Paste 2-1 Time , And then put 22 As a whole , Copy 1 Time , Paste 3-1 Time , Copy again 1 Time , Paste 2-1 Time . common 2x2+3x2 = 10 Time
Code :
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; // Look at how many times the prime factor has been used
while (n % i == 0) {
s++;
n /= i;
}
if (s > 0) {
res += i * s;
}
}
System.out.println(res);
}
}
边栏推荐
- [OC foundation framework] - string and date and time >
- 项目连接数据库遇到的问题及解决
- Problems encountered in connecting the database of the project and their solutions
- LeetCode:387. The first unique character in the string
- LeetCode41——First Missing Positive——hashing in place & swap
- In depth analysis and encapsulation call of requests
- CSP first week of question brushing
- Simclr: comparative learning in NLP
- 【每日一题】搬运工 (DFS / DP)
- Intel distiller Toolkit - Quantitative implementation 3
猜你喜欢
UML圖記憶技巧
Parameterization of postman
Intel distiller Toolkit - Quantitative implementation 3
Mise en œuvre de la quantification post - formation du bminf
Detailed explanation of dynamic planning
Advanced Computer Network Review(5)——COPE
SimCLR:NLP中的对比学习
【shell脚本】——归档文件脚本
How to intercept the string correctly (for example, intercepting the stock in operation by applying the error information)
LeetCode:236. The nearest common ancestor of binary tree
随机推荐
Cesium draw points, lines, and faces
Intel distiller Toolkit - Quantitative implementation 1
LeetCode:162. Looking for peak
LeetCode:387. The first unique character in the string
Multivariate cluster analysis
Using C language to complete a simple calculator (function pointer array and callback function)
Mise en œuvre de la quantification post - formation du bminf
Advance Computer Network Review(1)——FatTree
LeetCode:39. Combined sum
Digital people anchor 618 sign language with goods, convenient for 27.8 million people with hearing impairment
Tdengine biweekly selection of community issues | phase III
Once you change the test steps, write all the code. Why not try yaml to realize data-driven?
What is MySQL? What is the learning path of MySQL
Intel distiller Toolkit - Quantitative implementation 3
Pytest参数化你不知道的一些使用技巧 /你不知道的pytest
Pytest's collection use case rules and running specified use cases
[sword finger offer] serialized binary tree
Computer graduation design PHP Zhiduo online learning platform
Opencv+dlib realizes "matching" glasses for Mona Lisa
LeetCode:39. 组合总和