6930번 - Mod Inverse 다국어

문제

In many cryptographic applications, the Modular Inverse is a key point. This question involves finding the modular inverse of a number.

Given 0ドル < x < m,ドル where $x$ and $m$ are integers, the modular inverse of $x$ is the unique integer $n,ドル 0ドル < n < m,ドル such that the remainder upon dividing $x \times n$ by $m$ is 1ドル$.

For example, 4ドル \times 13 = 52 = 17 \times 3 + 1,ドル so the remainder when 52ドル$ is divided by 17ドル$ is 1ドル,ドル and thus 13ドル$ is the inverse of 4ドル$ modulo 17ドル$.

You are to write a program which accepts as input the two integers $x$ and $m,ドル and outputs either the modular inverse $n,ドル or the statement No such integer exists. if there is no such integer $n$.

입력

출력

제한

• $m \le 100$

힌트