問題一覧 > 通常問題

No.1203 お菓子ゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 16
作問者 : PCTprobabilityPCTprobability / テスター : hotmanwwhotmanww
2 ProblemId : 4791 / 出題時の順位表
問題文最終更新日: 2020-08-28 21:03:53

問題文

貴方はある人とゲームをします。 貴方は $A$ 個のガムを、相手は $B$ 個のガムを持っています。 ただし持っているガムの個数は同じではないです。 持っているガムの内、それぞれに一個だけすっぱいガムが入っていて、それを食べてしまったら負けであり、それがどれなのかは互いに把握していません。 ゲームの先手は持っているガムの個数が多い方です。 自分のガムを持っている個数が相手のガムを持っている個数より $1$ 個だけ少なくなるように自分のガムからランダムに選び食べます。 この操作を勝負がつくまで続けます。 貴方の勝つ確率が与えられるので、 $1 \le A,B \le 10^8,A \neq B$ を満たす正整数の組 $A,B$ としてあり得るものの個数を求めてください。 ただし $1$ 回の入力で $S$ 個のテストケースが与えられます。

入力

まず入力の個数 $S$ が与えられます。
$S$
その後 $S$ 行に渡り $S$ 個のテストケースが与えられます。
$X$ $Y$
これは貴方の勝つ確率が $\frac{X}{Y}$ ということです。

  • 入力は全て整数である。
  • $1 \le S \le 10^5$
  • $1\le X < Y \le 10^7$
  • $GCD(X,Y)=1$ であることが保証されます。

出力

最後に改行してください。

サンプル

サンプル1
入力
1
1 4
出力
25000000

サンプル2
入力
1
1 8
出力
12500000

サンプル3
入力
3
17 100
123 500
6 25
出力
1000000
200000
4000002

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。