回分類題庫
h125: C.棒球練習場
關鍵字: NPSC 2013 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 66 Times / 64 Users | Submit : 88 Times / 66 Users | Accepted rate : 97%
題目加入時間 : 2014-09-16 09:41

Content: 简体中文

公元四八八八年,由於空間傳送裝置的普及,人類對於能夠將物品傳送至不同空間,早就習以為常,並且作了許多應用。

有一天,皮皮和球球決定到「眼明手快」棒球場上進行終極棒球的決鬥。這場決鬥的規則很簡單,打到最多球的人就贏了。不過有趣的事情是,當棒球出現在某個位置 (x, y) 之後,下一秒,棒球就會被瞬間傳送到 (x ⊕ y, |x − y|) 的位置。其中 ⊕ 是把 x 和 y 寫成二進位以後進行 XOR 運算的意思。

舉個例子來說,一開始的球出現在 (5, 3) 的位置,那麼過了一秒以後就會出現在 (6, 2),再下一秒就會出現在 (4, 4),第四秒就會在 (0, 0) 了。

皮皮和球球經過了詳盡的觀察以後,發現了一件事:只要 x = y,下一秒球就會出現在 (0, 0)。於是,皮皮和球球打算在 (0, 0) 這個位置守株待球,只要球一出現,就可以把它打出去!

請你幫忙算算,若現在球的初始位置 (a, b) 滿足:1 ≤ a ≤ N 且 1 ≤ b ≤ M,那麼有哪些位置的球經過一段時間之後就會出現在 (0, 0) 呢?

Input:

輸入的第一行有一個正整數 T (T ≤ 50),代表測試資料的組數。

每一筆測試資料,包含兩個正整數 N, M(1 ≤ N, M ≤ 10000),中間以一個空白隔開。 

Output:

對於每一筆測試資料請輸出一行,包含一個整數,表示有幾球會出現在 (0, 0)。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
3 4
2 5
514 217

Sample Output :

12
10
111538

Hint :

Author :

NPSC 2013 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum