题目分析本题模拟了一种名为 “球钟” 的计时装置。该装置通过钢球在轨道上的移动来记录时间其核心机制如下一个队列存放待使用的钢球。三个栈或轨道分别表示分钟指示器可容纳444个球、五分钟指示器可容纳111111个球和小时指示器可容纳111111个可移动球外加111个固定球用于显示111到121212小时。每分钟从队列头部取出一个球并将其放入分钟指示器栈中。当分钟指示器栈满已有444个球时放入第555个球会触发该轨道的倾斜。此时分钟栈中的444个球按照后进先出LIFO\texttt{LIFO}LIFO的顺序返回队列末尾而触发倾斜的第555个球则被移动到五分钟指示器栈中。五分钟指示器和小时指示器的运作逻辑与此类似满溢后会将球按LIFO\texttt{LIFO}LIFO顺序退回队列并将当前球移动到下一级轨道。题目要求对于给定的初始钢球数量NNN范围在272727到700070007000之间计算出球钟的钢球序列在经过多少天以242424小时为周期即144014401440分钟后会首次回到其初始的排列顺序。解题思路解决这个问题的关键在于找到状态重复的周期。直接模拟直到状态重复可能会非常耗时但通过观察我们可以利用置换群Permutation Group\texttt{Permutation Group}Permutation Group的理论来高效求解。模拟一个完整周期我们首先模拟一天24×60144024 \times 60 144024×601440分钟的球钟运作。初始时队列中包含编号为000到N−1N-1N−1的球。经过144014401440次“取球-放球”操作后队列中的球会形成一个全新的排列。此时队列前端的球就是最初位于位置iii的球经过一天后的新位置。我们记录这个映射关系得到一个长度为NNN的置换数组permutation其中permutation[i]表示原始第i个球在一天后所在的位置。寻找循环节整个球钟的状态变化可以看作是一个置换的不断应用。根据置换群的性质整个系统回到初始状态所需的最小周期等于所有独立循环节长度的最小公倍数LCM\texttt{LCM}LCM。我们将permutation数组分解成若干个不相交的循环。例如一个循环i→permutation[i]→permutation[permutation[i]]→⋯→ii \to permutation[i] \to permutation[permutation[i]] \to \dots \to ii→permutation[i]→permutation[permutation[i]]→⋯→i的长度记为length。该循环中的球每经过length天就会回到各自的原位。计算结果最终所需的天数days就是所有循环节长度的LCM\texttt{LCM}LCM。由于结果可能非常大需要使用646464位整数long long\texttt{long long}long long来存储。在计算LCM(a,b)\texttt{LCM}(a, b)LCM(a,b)时为了防止溢出我们采用公式LCM(a,b)a/GCD(a,b)×b\texttt{LCM}(a, b) a / \texttt{GCD}(a, b) \times bLCM(a,b)a/GCD(a,b)×b进行计算。代码实现// Tempus et mobilius. Time and motion// UVa ID: 239// Verdict: Accepted// Submission Date: 2016-05-24// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 计算最大公约数GCDlonglonggcd(longlongx,longlongy){longlongt;while(x%y){tx;xy;yt%y;}returny;}intmain(intargc,char*argv[]){intn;while(cinn,n){queueintballs;// 待处理的球的队列stackintminute,five,hour;// 分钟、五分钟、小时指示器栈// 初始化将编号为0到n-1的球放入队列for(inti0;in;i)balls.push(i);// 模拟一天24小时 1440分钟的球钟运作for(inti0;i24*60;i){// 每分钟从队列头部取出一个球intballballs.front();balls.pop();// 放入分钟指示器栈if(minute.size()4)minute.push(ball);else// 分钟指示器已满已有4个球{// 将分钟栈中的4个球按后进先出顺序退回队列末尾while(minute.empty()false){balls.push(minute.top());minute.pop();}// 将触发倾斜的第5个球放入五分钟指示器栈if(five.size()11)five.push(ball);else// 五分钟指示器已满已有11个球{// 将五分钟栈中的11个球按后进先出顺序退回队列末尾while(five.empty()false){balls.push(five.top());five.pop();}// 将触发倾斜的第12个球放入小时指示器栈if(hour.size()11)hour.push(ball);else// 小时指示器已满已有11个可移动球{// 将小时栈中的11个球按后进先出顺序退回队列末尾while(hour.empty()false){balls.push(hour.top());hour.pop();}// 触发倾斜的第12个球也退回队列末尾balls.push(ball);}}}}// 经过一天的模拟后balls队列中存储了新的排列。// permutation[i] 记录了原始第i个球在一天后的位置。intpermutation[7010],visited[7010]{};// 从队列中读取这个置换映射for(inti0;in;i){permutation[i]balls.front();balls.pop();}// 计算所有循环节长度的最小公倍数LCMlonglongdays1;for(inti0;in;i)if(visited[i]0)// 找到一个未访问的球即一个新循环的起点{intlength1;// 记录当前循环的长度visited[i]1;// 沿着置换追踪直到回到起点for(intjpermutation[i];j!i;jpermutation[j]){visited[j]1;length;}// 计算当前总天数与当前循环长度的最小公倍数// 使用公式 LCM(a, b) a / GCD(a, b) * b 防止溢出daysdays/gcd(days,length)*length;}// 按照题目要求的格式输出结果coutn balls cycle after days days.\n;}return0;}