Submit solution

Points:
3

Time limit:
2.0s

Memory limit:
64M

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

##### 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 , where and are integers, the modular inverse of is the unique integer , , such that the remainder upon dividing by is .

For example, , so the remainder when is divided by is , and thus is the inverse of modulo .

You are to write a program which accepts as input the two integers and , and outputs either the modular inverse , or the statement `No such integer exists.`

if there is no such integer .

#### Constraints

#### Sample Input 1

```
4
17
```

#### Sample Output 1

`13`

#### Sample Input 2

```
6
10
```

#### Sample Output 2

`No such integer exists.`

## Comments

This comment is hidden due to too much negative feedback. Click here to view it.

Is this a looping problem?

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

This comment is hidden due to too much negative feedback. Click here to view it.

Your solution runs in time though

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

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

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.

I don't get this problem, is it supposed to say + instead of x? -> such that the remainder upon dividing x×n by m is 11.