UVa 616 Coconuts Revisited

题目描述一个经典问题改编自本·艾姆斯·威廉姆斯的短篇小说《椰子》。故事讲述五个人和一只猴子遭遇海难他们在岛上度过第一个夜晚收集椰子。晚上一个人醒来决定取走他的那份。他把椰子分成五堆剩下一个给了猴子然后藏起自己的那份继续睡觉。随后第二个人醒来做了同样的事情将椰子分成五堆剩一个给猴子藏起一份。第三、第四、第五个人也依次照做。第二天早上他们醒来后将剩下的椰子分成五等份这次没有剩余。问最初收集了多少椰子最小的答案是312131213121。但本题不是求这个。现在反过来如果知道最初收集的椰子数问最多能有多少个人和一只猴子参与这个过程使得上述过程能够发生输入格式输入包含一系列整数每行一个表示收集的椰子总数。输入以负数结束。输出格式对于每个椰子数输出最大可能的人数格式为X coconuts, Y people and 1 monkey如果没有可行解则输出X coconuts, no solution样例输入25 30 3121 -1输出25 coconuts, 3 people and 1 monkey 30 coconuts, no solution 3121 coconuts, 5 people and 1 monkey题目分析设椰子总数为NNN人数为pppp≥2p \ge 2p≥2。晚上有ppp个人依次醒来每次操作如下当前椰子数为xxx。此人将xxx分成ppp堆若x mod p1x \bmod p 1xmodp1则余下111个给猴子然后取走其中一堆即拿走x−1p\frac{x-1}{p}px−1​个剩下的椰子数为x′x−1−x−1p(x−1)⋅p−1p x x - 1 - \frac{x-1}{p} (x-1) \cdot \frac{p-1}{p}x′x−1−px−1​(x−1)⋅pp−1​若x mod p≠1x \bmod p \neq 1xmodp1则过程无法继续。共进行ppp次这样的操作ppp个人各一次。最后第二天早上将剩下的椰子分成ppp等份要求刚好分完即最后剩下的椰子数yyy满足y mod p0y \bmod p 0ymodp0。我们需要找到最大的ppp使得上述递推过程能够完整执行。观察第一次操作初始NNN必须满足N mod p1N \bmod p 1Nmodp1即N−1N-1N−1能被ppp整除。因此ppp必定是N−1N-1N−1的一个因子p1p 1p1。于是我们可以枚举N−1N-1N−1的所有因子从大到小尝试找到第一个满足完整过程的ppp即为最大人数。模拟过程时对于候选ppp按照递推式逐步计算ppp次每次检查是否满足x mod p1x \bmod p 1xmodp1若满足则更新xxx否则失败。完成ppp步后检查x mod px \bmod pxmodp是否为000。解题思路读入椰子数NNN若N0N 0N0则结束。特殊情况若N≤2N \le 2N≤2没有可行解因为至少需要222人。若N3N 3N3只有222人可行第一个人醒来拿走一个给猴子剩下两个分成两份一份一个拿走一个还剩下一个第二个人醒来拿走一个给猴子剩下零个分成两份都是零个拿走零个剩下零个第二天醒来剩下零个椰子可以平分符合题目要求。一般情况令MN−1M N - 1MN−1求MMM的所有因子从222开始。将所有因子按降序排列依次尝试。对于每个候选ppp模拟ppp次操作令xNx NxN。循环ppp次检查(x−1) mod p(x - 1) \bmod p(x−1)modp是否为000若不是则失败。更新x(x−1)⋅(p−1)/px (x - 1) \cdot (p - 1) / px(x−1)⋅(p−1)/p。完成ppp次后检查x mod px \bmod pxmodp是否为000若是则ppp可行。第一个可行的ppp即为最大人数输出若无则输出无解。复杂度分析求N−1N-1N−1的因子O(N)O(\sqrt{N})O(N​)。每个因子模拟ppp次操作总次数不超过因子个数×\times×最大因子但因子个数远小于N\sqrt{N}N​且ppp也远小于NNN。总体时间复杂度可以接受。空间复杂度O(N)O(\sqrt{N})O(N​)。代码实现// Coconuts Revisited// UVa ID: 616// Verdict: Accepted// Submission Date: 2016-08-28// UVa Run Time: 0.070s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,nn;while(cinn,n0){nnn;if(n2){coutn coconuts, no solution\n;continue;}if(n3){cout3 coconuts, 2 people and 1 monkey\n;continue;}n--;vectorintbigger,smaller;intup_limitsqrt(n);for(inti2;iup_limit;i)if(n%i0){bigger.push_back(n/i);smaller.insert(smaller.begin(),i);}for(inti0;ismaller.size();i)bigger.push_back(smaller[i]);boolsolutionFoundfalse;for(inti0;ibigger.size();i){inttimes0,peoplebigger[i];nnn;while(true){n--;if(n%people0)n(n/people)*(people-1);elsebreak;times;if(n%people0||timespeople)break;}if(timespeoplen%people0){coutnn coconuts, people people and 1 monkey\n;solutionFoundtrue;break;}}if(!solutionFound)coutnn coconuts, no solution\n;}return0;}总结本题通过对椰子数进行逆向模拟利用第一次操作必须满足N−1N-1N−1能被人数整除这一关键条件从而将人数限制在N−1N-1N−1的因子范围内。枚举所有因子并模拟完整过程即可求得最大可行人数。该解法简洁高效关键在于理解递推关系和枚举范围的缩小。注意特殊情况N3N3N3和N≤2N \le 2N≤2的处理。