Dotcpp  >  编程题库  >  蓝桥杯2023年第十四届省赛真题-翻转硬币
题目 3149:

蓝桥杯2023年第十四届省赛真题-翻转硬币

时间限制: 3s 内存限制: 320MB 提交: 501 解决: 25

题目描述

给定 n 个按顺序摆好的硬币，一开始只有第 1 个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数 i 并将所有满足 j mod i = 0 的位置 j 的硬币翻转。
求最少需要多少次操作可以让所有硬币都朝上。

输入格式

输入一行包含一个整数 n 。

输出格式

输出一行包含一个整数表示最少需要的操作次数。

样例输入

7

样例输出

6

提示

对于 30% 的评测用例，n ≤ 5 × 106 ；

对于 70% 的评测用例，n ≤ 109 ；
对于所有评测用例，1 ≤ n ≤ 1018。


标签
 
分享 

                
                
                

                                        

                        
                        

                                                            
                                                        
                            
                            
                            
                        

                    

                    

                        
                    

                


                


                


                

                  上一题
                  下一题
                


            

            


                    

                        

                            
通过率

                        

                                                
                       
                    

                                        

                        

                            
统　计

                        

                        

                    

                    

                        

                            
解题报告

                        

                                                
                    


                    

                        

                            
推荐题目

                        

                        

                            

                            
蓝桥杯2022年第十三届决赛真题-卡牌
蓝桥杯2016年第七届真题-四平方和
蓝桥杯2016年第七届真题-压缩变换
蓝桥杯2016年第七届真题-最大比例
蓝桥杯2018年第九届真题-航班时间