<center>

问题 C: Boxes and Balls

时间限制: 1 Sec  内存限制: 64 MB
提交: 11  解决: 8

</center>

题目描述

Tom’s friend Jerry, from KBW, just showed him a great magic trick. At the beginning of the trick, there is one box on the ground with some number of balls in it. Jerry then performs this operation over and over again: 
1. put a new empty box down on the ground 
2. move one ball from each other box into that new empty box 
3. remove any boxes that are now empty 
4. sort the boxes in nondecreasing order by the number of balls in them Tom noticed that it is possible for this operation to leave the state of the boxes and balls unchanged! 
For example:
 • Suppose that at the beginning of the trick, the one box contains 3 balls.
 • In the first operation, Jerry adds a new empty box, puts 1 ball from the existing box into it, and sorts the boxes, so after that operation, there will be 2 boxes on the ground, one with 1 ball and one with 2 balls.
 • In the second operation, Jerry adds a new empty box and puts 1 ball from each of the existing 2 boxes into it; this creates one empty box, which Jerry removes, and then he sorts the boxes. So there are 2 boxes on the ground, one with 1 ball and one with 2 balls. But this is exactly the state that was present before the second operation! 
Tom thought about the trick some more, and realized that for some numbers of balls, it is not possible for the operation to leave the state unchanged. For example, if there are 2 balls at the beginning, then after one operation, there will be two boxes with 1 ball each, and after 2 operations, there will be one box with 2 balls, and so on, alternating between these two states forever. 
Tom looked around in his room and found infinitely many empty boxes, but only N balls. What is the maximum number of those balls that he could use to perform this trick, such that one operation leaves the state unchanged? 

输入

The first line of the input gives the number of test cases, T. T lines follow. 
Each line consist of one integer N, the number of balls Tom could find. 
Limits: • 1 ≤ T ≤ 100. • 1 ≤ N ≤ 1018 .

输出

For each test case, output one line containing ‘Case #x: y’, where x is the test case number (starting from 1) and y is the maximum number of balls that Tom could use to perform the trick, as described above.  

样例输入

3
1
2
3

样例输出

Case #1: 1
Case #2: 1
Case #3: 3

思路：

找规律的题，很容易找出来规律就是，1，12，123，1234，这样的情况才能无限循环。所以输出任意一数m，先解方程n(n+1)/2=m，得出来解的取整整数，然后取整的数再算n(n+1)/2与m进行比较，如果比m大则说明这个数找大了，就往下减一个数即为所求。如果小于等于m，则说明这个取整数则是符合条件的最大的那个数。



代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;

int main()
{
	//freopen("in.txt","r",stdin);
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
	   	printf("Case #%d: ",i);
     	long long n;
	    scanf("%lld",&n);
	    long long re = (sqrt(1 + 8 * n) - 1) / 2;
	    long long ans = re * (re + 1) / 2;
	    if (ans <= n) ans = ans; 
	    printf("%lld\n",ans);	
	}	
	return 0;
}