1441 . 獅子王棋
TopCoder
Tags
Description
有一天 GrandLion 跟 GrandTiger 在非洲大草原奔跑的時候，發現了一個棋盤遊戲，叫做「獅子王棋」（LionKingChess）。
這個棋盤有 $N$ 個格子跟一個棋子，編號為 $1,2,\dots,N$，規則如下：一開始所有格子都是未被拜訪過的，GrandLion 首先先把棋子放到一個格子上，並把這個格子標記為拜訪過，接下來由 GrandTiger、GrandLion 輪流移動棋子，GrandTiger 先動。
假設棋子目前在編號 $i$ 的格子，這輪移動棋子的人如果想要把棋子移到編號 $j$ 的格子，必須要滿足編號 $j$ 的格子未被拜訪過，並且 $L\le |i-j|\le R$，將棋子移動到編號 $j$ 的格子後，要把格子標記為拜訪過。
最先無法移動棋子的人就輸了，另外一位玩家獲勝，GrandLion 想要知道有多少正整數數對 $(L,R)$，滿足 $1\le L\le R\le N$，可以使他有必勝策略。
Input Format
第一行輸入一個正整數 $t$，代表測資數量。
接下來 $t$ 行，每行輸入一個正整數 $N$。
- $1\le t\le 100$
- $1\le N\le 10 ^ 9$
Output Format
對於每筆測資，輸出可以滿足條件的正整數數對 $(L,R)$ 的數量。
Sample Input 1
3 1 2 3
Sample Output 1
1 1 6
Sample Input 2
6 114 200 514 88888 993244858 1000000000
Sample Output 2
2130 6476 42796 1273934597 159062563889592374 161233516854071850
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 2~14 | $N$ 是奇數 | 3 |
| 3 | 15~19 | $N \le 50$ | 24 |
| 4 | 15~25 | $N \le 5\times 10 ^ 5$ | 47 |
| 5 | 0~34 | 無特別限制。 | 26 |