Time limit: 2.0s
Memory limit: 256M
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 .
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
No such integer exists.
For me how did I forget there might be a multiple of outputs lol
I spent two hours head scratching before I realised that I had no output for if there was no possible modinverse. Kill me
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