No.3133 Inverse Modulo B
Problem Statement
You are given a non-negative integer $N$ and a positive integer $B$.
Determine whether there exists a non-negative integer $i$ satisfying $Ni \equiv 1 \pmod{B}$, and if one exists, find the minimum such $i$.
Here, for non-negative integers $n,m$, $n \equiv m \pmod{B}$ means that there exists an integer $k$ satisfying $n - m = kB$.
Input
The input is given from standard input in $1$ line in the following format:
- The $1$st line contains $N, B$ separated by a single space.
$N$ $B$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $0 \leq N \leq 10^{19}$.
- $B$ is an integer satisfying $1 \leq B \leq 10^6$.
Output
If there exists a non-negative integer $i$ satisfying $Ni \equiv 1 \pmod{B}$, print the minimum such $i$ in $1$ line; otherwise, print NaN.
Print a newline at the end.
Sample
Sample 1
Input
1 1
Output
0
Here $(N,B) = (1,1)$. If we set $i = 0$, then $i$ is a non-negative integer and satisfies $Ni = 0 \equiv 1 \pmod{B}$. Since there is no non-negative integer smaller than $0$, $0$ is the minimum non-negative integer satisfying the condition imposed on $i$ in the problem statement.
Sample 2
Input
0 2
Output
NaN
Here $(N,B) = (0,2)$. For any non-negative integer $i$, we have $Ni = 0 \not\equiv 1 \pmod{B}$.
Sample 3
Input
1 2
Output
1
Here $(N,B) = (1,2)$. If we set $i = 1$, then $i$ is a non-negative integer and satisfies $Ni = 1 \equiv 1 \pmod{B}$. The only non-negative integer smaller than $1$ is $0$, and $0$ does not satisfy the condition imposed on $i$ in the problem statement, so $1$ is the minimum non-negative integer satisfying the condition.
Sample 4
Input
2 3
Output
2
Here $(N,B) = (2,3)$. If we set $i = 2$, then $i$ is a non-negative integer and satisfies $Ni = 4 \equiv 1 \pmod{B}$. The only non-negative integers smaller than $2$ are $0,1$, and neither of $0,1$ satisfies the condition imposed on $i$ in the problem statement, so $2$ is the minimum non-negative integer satisfying the condition.
Sample 5
Input
2 4
Output
NaN
Here $(N,B) = (2,4)$. For any non-negative integer $i$, we have $Ni \equiv 0 \not\equiv 1 \pmod{2}$, and since $2$ is a divisor of $B$, in particular $Ni \not\equiv 1 \pmod{B}$.
Sample 6
Input
10000000000000000000 7
As shown here, $N$ may not fit in a 32-bit integer.
Output
5
Here $(N,B) = (10^{19},7)$. If we set $i = 5$, then $i$ is a non-negative integer and satisfies $Ni = 5 \times 10^{19} \equiv 1 \pmod{B}$. None of the non-negative integers smaller than $5$ satisfies the condition imposed on $i$ in the problem statement, so $5$ is the minimum non-negative integer satisfying the condition.
Note that $5 \times 10^{19}$, which appears in the intermediate calculation, does not fit even in a 64-bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。