問題一覧 > 教育的問題

No.3133 法B逆元

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : 👑 p-adic / テスター : Taka
2 ProblemId : 10691 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-03 20:12:42

問題文

非負整数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。