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

时间限制: s 内存限制: MB 提交: 501 解决: 25
题目描述
给定 n 个按顺序摆好的硬币，一开始只有第 1 个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数 i 并将所有满足 j mod i = 0 的位置 j 的硬币翻转。
求最少需要多少次操作可以让所有硬币都朝上。
输入
输入一行包含一个整数 n 。
输出
输出一行包含一个整数表示最少需要的操作次数。
样例输入
7
样例输出
6
提示

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

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



                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
尽可能可能会加不加班GVv看吧过于高抗压液体肥人多热水的无色特色台湾色娃娃
                        

                    

                

                

                    

                        
比赛状况