HDOJ 5591 ZYB's Game

ZYB's Game
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 297    Accepted Submission(s): 249
Problem Description
ZYB played a game named
NumberBomb with his classmates in hiking:a host keeps a number in
[1,N] in mind,then
players guess a number in turns,the player who exactly guesses
X loses,or the host will tell all the players that
the number now is bigger or smaller than
X .After that,the range players can guess will decrease.The range is
[1,N] at first,each player should guess in the legal range.
Now if only two players are play the game,and both of two players know the
X ,if two persons all use the best strategy,and the first player guesses first.You are asked to find the number of
X that the second player
will win when
X is in
[1,N] .
 
Input
In the first line there is the number of testcases
T .
For each teatcase:
the first line there is one number
N .
1≤T≤100000 ,
1≤N≤10000000
 
Output
For each testcase,print the ans.
 
Sample Input

   
   
   
   

    
    
    
    1
3
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1
   
   
   
   

 
タイトル:
ZYB
遠足の中で、同級生たちと「デジタル爆弾」ゲームをしました.司会者の心の中で「1,N」の中の数字XXを考えて、それからプレイヤーたちは交代で1つの数字を当てて、もし1人のプレイヤーがちょうどXXを当てたらマイナスになります.そうしないと、司会者は会場の人に現在の数とX比が大きいか小さいかを教えて、それから推測の範はそれに応じて減少して、最初の範囲は「1,N][1,N」です..各プレイヤーは合法的な范囲の中で推測するしかない.今仮に2人だけがこのゲームを游んでいると仮定して、しかも2人はすでに最后のXXを知っていて、もし2人はすべて最も良い策略を取るならば.Xin[1,N]X∈[1,N]の中で后手の勝利のXXの数を求めます.
考え方:左右の2つの石に比べて、毎回1つの山の中で任意の多くを取ることができて、取った人は勝利します.左右の2つの石が同時になると、私たちは簡単にすることができます
构造后の手の胜利の方法:つまり别の1山の石の中で同じ多くの石を取って、さもなくば、先手はいくつかの石を取って2山の石を同じにすることができます.だから、Nが奇数で1を出力して、さもなくば00を出力します.
acコード:

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#define MAXN 60001
#define LL long long
#define INF 0xfffffff
#define fab(x) (x)>0?(x):(-x)
#define mem(x) memset(x,0,sizeof(x))
#define PI acos(-1)
using namespace std;
int main()
{
	int n,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		printf(n%2?"1
":"0
");
	}
	return 0;
}