P9748 [CSP-J 2023] 小苹果

P9748 [CSP-J 2023] 小苹果此篇仅为记录我的思考防止我以后忘记如果能对你产生帮助荣幸之至题目描述小Y{\text{Y}}Y的桌子上放着n{\text{n}}n个苹果从左到右排成一列编号为从1{\text{1}}1到n{\text{n}}n。小苞是小Y{\text{Y}}Y的好朋友每天她都会从中拿走一些苹果。每天在拿的时候小苞都是从左侧第1{\text{1}}1个苹果开始、每隔2{\text{2}}2个苹果拿走1{\text{1}}1个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。小苞想知道多少天能拿完所有的苹果而编号为n{\text{n}}n的苹果是在第几天被拿走的输入格式输入的第一行包含一个正整数n{\text{n}}n表示苹果的总数。输出格式输出一行包含两个正整数两个整数之间由一个空格隔开分别表示小苞拿走所有苹果所需的天数以及拿走编号为n{\text{n}}n的苹果是在第几天。输入输出样例输入8输出55数据范围对于100%{ 100 \% }100%的数据1≤n≤109{1 \le n \le 10^9}1≤n≤109个人解析因为n≤109{n \le 10^9}n≤109所以用数组或链表去模拟貌似不太可能简单从数列规律上观察一下索引1\textcolor{red}{1}1234\textcolor{red}{4}4567\textcolor{red}{7}78第 1 轮前12345678第 1 轮后23568第 2 轮后358第 3 轮后58第 4 轮后8第 5 轮后因为每隔两个就拿一个所以消失的数字是以3{3}3为周期的规律消失的数字8{8}8变成了第5{5}5个数前面消失了三个数字每次消失的数字的当前序号均为3{3}3的倍数1{1}1。那也就是说如果可以知道n{n}n及n{n}n以内有多少个%31\text{\%31}%31的数字那么就可以知道一轮后还剩几个数字苹果特殊的当n%31{n\%31}n%31时n{n}n会被拿走例如7%31{7\%31}7%317{7}7在第一轮就被拿走了之前写过一道题问的是n{n}n以内有多少个数字i{i }i满足i%xy{i\%xy}i%xy比如计算1...19{1 ... 19}1...19以内有多少个%42{\%42}%42的数字先思考1...19{1 ... 19}1...19以内有多少个%40{\%40}%40的数字想象成一条n19{n19}n19米的线段每x4{x4}x4米就裁一段那么一共可以裁19/44{19/44}19/44段余3{3}3米{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16},{17,18,19}\text{\{1,2,3,4\},\{5,6,7,8\},\{9,10,11,12\},\{13,14,15,16\},\{17,18,19\}}{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16},{17,18,19}那假如我先藏起来y2{y2}y2米其后还是每x4{x4}x4米就裁一段每完整一段的末尾数字会满足%xy{\%xy}%xy{1,2}\text{\{1,2\}}{1,2}被藏起来{3,4,5,6},{7,8,9,10},{11,12,13,14},{15,16,17,18},{19}\text{\{3,4,5,6\},\{7,8,9,10\},\{11,12,13,14\},\{15,16,17,18\},\{19\}}{3,4,5,6},{7,8,9,10},{11,12,13,14},{15,16,17,18},{19}现在有(19-2)/44\text{(19-2)/44}(19-2)/44个完整的线段末尾分别是6,10,14,18\text{6,10,14,18}6,10,14,18结尾加上手里藏起来的2\text{2}2共5\text{5}5个数字满足%42{\%42}%42那么算法等同于⌊n−yx⌋1{ \left\lfloor \frac{n - y}{x} \right\rfloor 1 }⌊xn−y​⌋1非本题的情况下n−y{n-y}n−y需要特判一下。设某一天操作前当前剩余苹果总数为nnn个因此当天操作结束后剩余苹果数量为n新n−(⌊n−13⌋1)n_{\text{新}} n - \left( \left\lfloor \frac{n-1}{3} \right\rfloor 1 \right)n新​n−(⌊3n−1​⌋1)每天重复这个更新操作直到苹果数变为0累计的轮数就是总天数。参考程序#includeiostreamusingnamespacestd;intn,cnt,f;intmain(){cinn;while(n){cnt;if(!fn%31)fcnt;nn-(n-1)/3-1;}coutcnt f;return0;}时间复杂度初始值为NNN第kkk轮后nk≤N⋅(23)kn_k \le N\cdot \left(\frac23\right)^knk​≤N⋅(32​)k直到nk0n_k0nk​0停止N⋅(23)k≤1N\cdot \left(\frac23\right)^k \le 1N⋅(32​)k≤1两边取对数k≥ln⁡Nln⁡32k \ge \frac{\ln N}{\ln \frac32}k≥ln23​lnN​迭代总轮数kO(log⁡N)kO(\log N)kO(logN)底数是常数32\frac3223​对数复杂度和底数无关统一记作O(log⁡n)O(\log n)O(logn),因此整体时间复杂度为O(log⁡n)\boldsymbol{O(\log n)}O(logn)。A c c e pted\colorbox{#52C41A}{\color{white}{\Huge{\ A \hspace{-.4cm}{\raisebox{.3cm}{c}} \hspace{-.3cm}{c} \normalsize\hspace{-.3cm}{e} \Huge{\hspace{-.1cm}{p}}{t}ed}}}Accepted​