开发工具:
文件大小: 505byte
下载次数: 0
上传时间: 2012-11-01
详细说明：11075 强盗分赃
时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: 无限制
Description
有天夜里5个强盗A、B、C、D、E抢到一大堆金币（金币个数不超过n个，n<=100000000），可是怎么也无法平均分成5份，吵吵嚷嚷……
吵累了，只好先睡觉，准备第二天再分。
夜深了，一个强盗A偷偷爬起来，先拿了一个金币私下放自己口袋藏好，再将金币分为5等份，将自己的那一份再私藏好就去睡觉了。
随着第二个强盗B也爬起来，也是私拿了一个金币再分5等份，也私藏起自己那份就睡觉去了。
后来的三个强盗C、D、E也都是这样办的。
问最初有多少个金币？（最初的金币个数有多种可能，请输出n以内所有可能，从小到大排列）
Input
输入一个数，n。
请输出金币数不超过n的可能的初始金币个数。Output
初始金币个数的多种可能（初始金币个数小于等于n）。
请输出不超过n的“所有的”可能，从小到大排列出，中间空格相连。
如果不超过n没有一种可能，输出impossible（无标点，无大写）
例如输入10，则输出impossible
Sample Input
8000
Sample Output
3121 6246
Hint
此题所说的是：每个强盗私拿1个金币后都可以五等分，再私藏起1份，留下4份。
这样的初始金币个数是怎样的数，才能满足这个条件。
方法一：
此题若仅采用程序实现的话是较为简单的，可使用递归算法，或循环处理。递归算法如下（循环处理也很简单）：
int count = 0;
int func(int num) //判断初始为num的数是否合适
{
int temp = num-1;
if(temp%5 == 0 && count<5)
{
count++;
return func(temp/5*4);
}
else
if (count==5)
return 1;
else
return 0;
}
但若要分析初始金币个数的通项函数表达就更难一些：
方法二：
从最后一个强盗往前考虑，假设到第五个强盗E时，平均每个强盗得到x个金币
第五个强盗E藏掉一个金币后剩5x个
第四个强盗D藏掉一个金币后剩5(5x+1)/4=25x/4+5/4
第三个强盗C藏掉一个金币后剩5(25x/4+5/4+1)/4=125x/16+45/16
第二个强盗B藏掉一个金币后剩5(125x/16+45/16+1)/4=625x/64+305/64
第一个强盗A藏掉一个金币后剩5(625x/64+305/64+1)/4=3125x/256+1845/256
原来共有金币3125x/256+1845/256+1=3125x/256+2101/256=(12x+8)+53(x+1)/256
这里是突破口：53（x+1）/256 是整数，因金币数是整数，所以x=255时最小的初始金币总数3121个。
方法三：或者这样分析，设金币总数n，由于5个强盗都是先藏一个后，发现余下的金币刚好均分5份，
所以设想在总数中加入4个新金币，则每个强盗占有的金币数不会改变（包括藏了的那一个），
从而每次分金币时这4个假想的金币会留存到后一层总数中，这使得每次分5份都是恰好的整数，
由此可见，n+4至少是5^5的整数倍，所以n的最小值为5^5-4=3121。
其余可能的n值为n=k*（5^5）+4，k为大于1的整数。
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
