B - Mod M Bet
Milk
2
s
1024
MB
1000
点
問題文
$0$ から $N - 1$ までの $N$ 種類の目が等確率で出るルーレットがあります。
このルーレットを回して出た目の数を $M$ で割ったあまりが $0$ になる確率を求めてください。
答えは互いに素な非負整数 $a, b$ を用いて $\displaystyle\frac{a}{b}$ と表せるので $(a, b)$ を求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて解いてください。
制約
- $1 \leq T \leq 10^5$
- $1\leq N, M \leq 10^{9}$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各ケースは以下の形式で与えられる。
$N \ \ M$
出力
$T$ 行出力せよ。
$i$ 行目には $i$ 番目のテストケースの答えを $(a, b)$ として、$a$ と $b$ をこの順に空白区切りで出力せよ。
入力例 1
3
6 100
6 4
1 1000000000
出力例 1
1 6
1 3
1 1
$1$ つ目のテストケースについて、ルーレットに書かれた出目は次の図のようになっています。
このルーレットを回して出た目の数を $100$ で割ったあまりが $0$ になる確率は $\displaystyle\frac{1}{6}$ なので、1 6 と出力します。
$2$ つ目のテストケースについて、ルーレットに書かれた出目は $1$ つ目の図と同様です。
答えは互いに素な非負整数の組で表さなければならないことに注意してください。