The task is the following. Given an integer x
(such that x
modulo 100000000003
is not equal to 0
) presented to your code in any way you find convenient, output another integer y < 100000000003
so that (x * y) mod 100000000003 = 1
.
You code must take less than 30 minutes to run on a standard desktop machine for any input x
such that |x| < 2^40
.
Test cases
Input: 400000001. Output: 65991902837
Input: 4000000001. Output: 68181818185
Input: 2. Output: 50000000002
Input: 50000000002. Output: 2.
Input: 1000000. Output: 33333300001
Restrictions
You may not use any libraries or builtin functions that perform modulo arithmetic (or this inverse operation). This means you can't even do a % b
without implementing %
yourself. You can use all other non-modulo arithmetic builtin functions however.
Similar question
This is similar to this question although hopefully different enough to still be of interest.
100000000003
? (just wondering) \$\endgroup\$