51Nod 1917 吃葡萄 c/c++题解

题目描述

在房间中G颗葡萄，现在有n个人。这n个人依次进入房间吃葡萄。每个人进去的时候都做如下操作，把葡萄分成n等份，发现还多出一颗，然后吃掉这一颗以及n等份中的一份，然后走出房间。这n个人吃完之后，最后房间里面的葡萄刚好可以分成n等分。问n最大是多少？
输入
多组测试数据。
第一行输入一个整数T(1<=T<=200)，表示测试数据的数目。
接下来T行，每一行一个整数G(1<=G<= 4000)
输出
对于每一组数据，输出一个整数表示最大的人数，如果无解输出No Solution。
输入样例
样例输入1
2
25
30
输出样例
样例输出1
3
No Solution

题解：

运用枚举法最关键的问题就是要找准枚举的范围，范围小了，可能有的测试点覆盖不到，范围大了，有可能会超时，这道题的枚举范围还是很好确定的：g个葡萄要分成n份，那n至少要从g开始枚举，所以第一重循环就是n的值从g->1开始枚举，每得到一个n，都要做一次O(n)的循环，来看是否每一次都能分出n份+1(g % n == 1 就表示可以分成n份多一个)，要注意：如果判断某一次不能这样分，就需要立即退出循环，否则会超时，**最后做一次判断，如果每一次都满足要求(flag = true)而且剩余的数量t_g%n == 0，说明n满足要求。**输出n即可，如果所有的n都不满足要求，就输出No Solution"。
(还有注意一个点，就是如果此时葡萄只有1个了，要分成2份也是可行的: 每一份0个，还多出1个)

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！