文件名称：11075强盗分赃
文件大小：505B
文件格式：TXT
更新时间：2015-11-22 06:39:06
强盗分赃
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的整数。