No.3133 法B逆元
タグ : / 解いたユーザー数 80
作問者 : 👑
p-adic
/ テスター :
Taka
問題文
非負整数 $N$ と正整数 $B$ が与えられます。
$Ni \equiv 1 \pmod{B}$ を満たす非負整数 $i$ が存在するか否かを判定し、存在する場合はそのような $i$ の最小値を求めてください。
ただし非負整数 $n,m$ に対し $n \equiv m \pmod{B}$ とは $n - m = kB$ を満たす整数 $k$ が存在するということを表します。
入力
入力は以下の形式で標準入力から $1$ 行で与えられます：
- $1$ 行目に $N, B$ が半角空白区切りで与えられます。
$N$ $B$
制約
入力は以下の制約を満たします：
- $N$ は $0 \leq N \leq 10^{19}$ を満たす整数である。
- $B$ は $1 \leq B \leq 10^6$ を満たす整数である。
出力
$Ni \equiv 1 \pmod{B}$ を満たす非負整数 $i$ が存在する場合はそのような $i$ の最小値を $1$ 行に出力し、存在しない場合はNaNと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1
出力
0
$(N,B) = (1,1)$ です。$i = 0$ と定めると、$i$ は非負整数であり $Ni = 0 \equiv 1 \pmod{B}$ を満たします。$0$ より小さい非負整数は存在しないので、$0$ は問題文で $i$ に課されている条件を満たす非負整数の最小値です。
サンプル2
入力
0 2
出力
NaN
$(N,B) = (0,2)$ です。いかなる非負整数 $i$ に対しても $Ni = 0 \not\equiv 1 \pmod{B}$ となります。
サンプル3
入力
1 2
出力
1
$(N,B) = (1,2)$ です。$i = 1$ と定めると、$i$ は非負整数であり $Ni = 1 \equiv 1 \pmod{B}$ を満たします。$1$ より小さい非負整数は $0$ のみであり、$0$ は問題文で $i$ に課されている条件を満たさないので、$1$ は条件を満たす非負整数の最小値です。
サンプル4
入力
2 3
出力
2
$(N,B) = (2,3)$ です。$i = 2$ と定めると、$i$ は非負整数であり $Ni = 4 \equiv 1 \pmod{B}$ を満たします。$2$ より小さい非負整数は $0,1$ のみであり、$0,1$ はいずれも問題文で $i$ に課されている条件を満たさないので、$2$ は条件を満たす非負整数の最小値です。
サンプル5
入力
2 4
出力
NaN
$(N,B) = (2,4)$ です。いかなる非負整数 $i$ に対しても $Ni \equiv 0 \not\equiv 1 \pmod{2}$ となり、$2$ は $B$ の約数であるので特に $Ni \not\equiv 1 \pmod{B}$ となります。
サンプル6
入力
10000000000000000000 7
このように $N$ が32bit整数の範疇に収まらないこともあります。
出力
5
$(N,B) = (10^{19},7)$ です。$i = 5$ と定めると、$i$ は非負整数であり $Ni = 5 \times 10^{19} \equiv 1 \pmod{B}$ を満たします。$5$ より小さい非負整数はいずれも問題文で $i$ に課されている条件を満たさないので、$5$ は条件を満たす非負整数の最小値です。
ここで、途中式で現れた $5 \times 10^{19}$ が64bit整数の範疇にも収まらないことに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。