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 \le 100~

Sample Input 1

4
17

Sample Output 1

Sample Input 2

6
10

Sample Output 2

No such integer exists.

Comments

1

MonkeyKang16 commented on Oct. 18, 2025, 3:40 p.m.

i found a function named pow that automates the mod inverse

-1

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

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

35

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

-6

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.

This comment is hidden due to too much negative feedback. Show it anyway.

8

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

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