CCC '01 J2 - Mod Inverse - Olympiads Online Judge

CCC '01 J2 - Mod Inverse

View as PDF

Submit solution

All submissions

Best submissions

Points: 3 (partial)

Time limit: 2.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2001 Stage 1, Junior #2

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$ $0 < x < m$ , where $x$ $x$ and $m$ $m$ are integers, the modular inverse of $x$ $x$ is the unique integer $n$ $n$ , $0 < n < m$ $0 < n < m$ , such that the remainder upon dividing $x \times n$ $x \times n$ by $m$ $m$ is $1$ $1$ .

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

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

Constraints

$m \le 100$ $m \leq 100$

Sample Input 1

Copy

4
17

Sample Output 1

Copy

Sample Input 2

Copy

6
10

Sample Output 2

Copy

No such integer exists.

Comments

0

20220680 commented on Sept. 12, 2022, 10:37 a.m.

For me how did I forget there might be a multiple of outputs lol

29

Subway_Man commented on Nov. 15, 2019, 1:08 a.m.

I spent two hours head scratching before I realised that I had no output for if there was no possible modinverse. Kill me

-2

harry7557558 commented on Oct. 19, 2019, 7:35 p.m.

I have heard an algorithm to find the mod inverse of a large integer in logarithm time.

7

Aaeria commented on Oct. 28, 2019, 3:11 a.m.

Yes, see the problem https://dmoj.ca/problem/modinv