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，人数为ppp（p≥2p \ge 2p≥2）。晚上有ppp个人依次醒来，每次操作如下：

• 当前椰子数为xxx。
• 此人将xxx分成ppp堆，若x mod p=1x \bmod p = 1xmodp=1，则余下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 p=0y \bmod p = 0ymodp=0。

我们需要找到最大的ppp，使得上述递推过程能够完整执行。

观察第一次操作：初始NNN必须满足N mod p=1N \bmod p = 1Nmodp=1，即N−1N-1N−1能被ppp整除。因此ppp必定是N−1N-1N−1的一个因子（p>1p > 1p>1）。于是我们可以枚举N−1N-1N−1的所有因子，从大到小尝试，找到第一个满足完整过程的ppp，即为最大人数。

模拟过程时，对于候选ppp，按照递推式逐步计算ppp次，每次检查是否满足x mod p=1x \bmod p = 1xmodp=1，若满足则更新xxx，否则失败。完成ppp步后，检查x mod px \bmod pxmodp是否为000。

解题思路

1. 读入椰子数NNN，若N<0N < 0N<0则结束。

2. 特殊情况：

   • 若N≤2N \le 2N≤2：没有可行解（因为至少需要222人）。
   • 若N=3N = 3N=3：只有222人可行（第一个人醒来，拿走一个给猴子，剩下两个，分成两份，一份一个，拿走一个，还剩下一个；第二个人醒来，拿走一个给猴子，剩下零个，分成两份，都是零个，拿走零个，剩下零个；第二天醒来，剩下零个椰子，可以平分，符合题目要求）。

3. 一般情况：令M=N−1M = N - 1M=N−1，求MMM的所有因子（从222开始）。将所有因子按降序排列，依次尝试。

4. 对于每个候选ppp，模拟ppp次操作：

   • 令x=Nx = Nx=N。
   • 循环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可行。

5. 第一个可行的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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,nn;while(cin>>n,n>=0){nn=n;if(n<=2){cout<<n<<" coconuts, no solution\n";continue;}if(n==3){cout<<"3 coconuts, 2 people and 1 monkey\n";continue;}n--;vector<int>bigger,smaller;intup_limit=sqrt(n);for(inti=2;i<=up_limit;i++)if(n%i==0){bigger.push_back(n/i);smaller.insert(smaller.begin(),i);}for(inti=0;i<smaller.size();i++)bigger.push_back(smaller[i]);boolsolutionFound=false;for(inti=0;i<bigger.size();i++){inttimes=0,people=bigger[i];n=nn;while(true){n--;if(n%people==0)n=(n/people)*(people-1);elsebreak;times++;if(n%people==0||times>people)break;}if(times==people&&n%people==0){cout<<nn<<" coconuts, "<<people<<" people and 1 monkey\n";solutionFound=true;break;}}if(!solutionFound)cout<<nn<<" coconuts, no solution\n";}return0;}

总结

本题通过对椰子数进行逆向模拟，利用第一次操作必须满足N−1N-1N−1能被人数整除这一关键条件，从而将人数限制在N−1N-1N−1的因子范围内。枚举所有因子并模拟完整过程，即可求得最大可行人数。该解法简洁高效，关键在于理解递推关系和枚举范围的缩小。注意特殊情况N=3N=3N=3和N≤2N \le 2N≤2的处理。