20
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ So a-(a/b)*b is fine? \$\endgroup\$ – immibis Jul 4 '17 at 10:31
  • \$\begingroup\$ @immibis That looks fine. \$\endgroup\$ – user9206 Jul 4 '17 at 11:03
  • \$\begingroup\$ tag: restricted code? \$\endgroup\$ – Felipe Nardi Batista Jul 4 '17 at 11:14
  • 1
    \$\begingroup\$ What's special about 100000000003? (just wondering) \$\endgroup\$ – NoOneIsHere Jul 4 '17 at 21:19
  • 1
    \$\begingroup\$ @Lembik In that case, could you mention that requirement that y<100000000003 in the question? \$\endgroup\$ – isaacg Jul 4 '17 at 21:25
16
\$\begingroup\$

Pyth, 24 bytes

L-b*/bJ+3^T11Jy*uy^GT11Q

Test suite

This uses the fact that a^(p-2) mod p = a^-1 mod p.

First, I manually reimplement modulus, for the specific case of mod 100000000003. I use the formula a mod b = a - (a/b)*b, where / is floored division. I generate the modulus with 10^11 + 3, using the code +3^T11, then save it in J, then use this and the above formula to calculate b mod 100000000003 with -b*/bJ+3^T11J. This function is defined as y with L.

Next, I start with the input, then take it to the tenth power and reduce mod 100000000003, and repeat this 11 times. y^GT is the code executed in each step, and uy^GT11Q runs it 11 times starting with the input.

Now I have Q^(10^11) mod 10^11 + 3, and I want Q^(10^11 + 1) mod 10^11 + 3, so I multiply by the input with *, reduce it mod 100000000003 with y one last time, and output.

\$\endgroup\$
  • \$\begingroup\$ Very nice indeed! \$\endgroup\$ – user9206 Jul 4 '17 at 7:56
  • \$\begingroup\$ I am guessing it's too late for me to tighten up the test cases.... \$\endgroup\$ – user9206 Jul 4 '17 at 9:45
  • 1
    \$\begingroup\$ @Lembik I'd do it anyways, but opinions may vary. It's your challenge, make it work the way you want it to. \$\endgroup\$ – isaacg Jul 4 '17 at 9:56
  • \$\begingroup\$ The way the question is written, it is possible you could drop the final reduction, although I asked for a clarification whether a result <100000000003 is required. \$\endgroup\$ – Ørjan Johansen Jul 4 '17 at 17:59
9
\$\begingroup\$

Haskell, 118 113 105 101 bytes

Inspired from this solution.

-12 from Ørjan Johansen

p=10^11+3
k b=((p-2)?b)b 1
r x=x-div x p*p
(e?b)s a|e==0=a|1<2=(div e 2?b$r$s*s)$last$a:[r$a*s|odd e]

Try it online!

Haskell, 48 bytes

A rewrite of this solution. While fast enough for the test vector, this solution is too slow for other inputs.

s x=until(\t->t-t`div`x*x==0)(+(10^11+3))1`div`x

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Awesome! I like the exponentiation by squaring approach. \$\endgroup\$ – isaacg Jul 4 '17 at 8:02
  • \$\begingroup\$ The shortest solution would be something like Try it online! but I don't think its performance is acceptable ... \$\endgroup\$ – bartavelle Jul 4 '17 at 8:05
  • \$\begingroup\$ (1) It's shorter to make g an operator (e?b)a s|... (2) If you switch a and s then you can make ! a non-operator and inline y into it. (3) You can get rid of the expensive where by a last trick, at the cost of duplicating z. Try it online! \$\endgroup\$ – Ørjan Johansen Jul 4 '17 at 9:02
  • \$\begingroup\$ Now those are nice tricks! \$\endgroup\$ – bartavelle Jul 4 '17 at 9:30
  • \$\begingroup\$ Oh, and |e==0=a gets rid of that pesky duplication. \$\endgroup\$ – Ørjan Johansen Jul 4 '17 at 9:43
6
\$\begingroup\$

Brachylog, 22 bytes

∧10^₁₁+₃;İ≜N&;.×-₁~×N∧

Try it online!

This took about 10 minutes for 1000000 with a slightly different (and longer) version of the code which was exactly two times faster (checked only positive values of İ instead of both positive and negatives). Therefore this should take about 20 minutes to complete for that input.

Explanation

We simply describe that Input × Output - 1 = 100000000003 × an integer, and let constraint arithmetic find Output for us.

∧10^₁₁+₃                   100000000003
        ;İ≜N               N = [100000000003, an integer (0, then 1, then -1, then 2, etc.)]
            &;.×           Input × Output…
                -₁         … - 1…
                  ~×N∧     … = the product of the elements of N

We technically do not need the explicit labeling , however if we do not use it, will not check the case N = [100000000003,1] (because it's often useless), meaning that this will be very slow for input 2 for example because it will need to find the second smallest integer instead of the first.

\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, I never would have expected constraint arithmetic to pull that off. Awesome! \$\endgroup\$ – isaacg Jul 4 '17 at 8:21
  • 1
    \$\begingroup\$ @isaacg The speed of this is unfortunately completely dependent on the value of İ, so this is still pretty slow for big products. \$\endgroup\$ – Fatalize Jul 4 '17 at 8:23
  • \$\begingroup\$ Updated the question. Does your code always take less than 30 minutes? \$\endgroup\$ – user9206 Jul 4 '17 at 9:59
6
\$\begingroup\$

Python, 53 51 49 58 53 49 bytes

-2 bytes thanks to orlp
-2 bytes thanks to officialaimm
-4 bytes thanks to Felipe Nardi Batist
-3 bytes thanks to isaacg
-1 byte thanks to Ørjan Johansen
-2 bytes thanks to Federico Poloni

x=input()
t=1
while t-t/x*x:t+=3+10**11
print t/x

Try it Online!

It took me ~30 minutes to figure this one out. My solution is to start with the first number that will mod to 1. This number is 1. If its divisible by x, then y is that number divided by x. If not, add 10000000003 to this number to find the second number which mod 1000000003 will equal 1 and repeat.

\$\endgroup\$
  • \$\begingroup\$ The first number that will mod to 1 is 1... \$\endgroup\$ – orlp Jul 4 '17 at 9:07
  • \$\begingroup\$ @orlp lol thanks. That saved me 2 bytes :) \$\endgroup\$ – Zachary Cotton Jul 4 '17 at 9:08
  • \$\begingroup\$ Interesting, on TIO this is fast for all the test cases but a bit random keyboard banging gave me 421385994 which times out. \$\endgroup\$ – Ørjan Johansen Jul 4 '17 at 9:10
  • \$\begingroup\$ @ØrjanJohansen Good sleuthing. \$\endgroup\$ – user9206 Jul 4 '17 at 9:11
  • 1
    \$\begingroup\$ If you need b only once, why not hardcoding it? \$\endgroup\$ – Federico Poloni Jul 4 '17 at 18:07
5
\$\begingroup\$

JavaScript (ES6), 153 143 141 bytes

Inspired by this answer from math.stackexchange.com.

A recursive function based on the Euclidean algorithm.

f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)

Modulo is implemented by computing:

quotient = Math.floor(a / b);
remainder = a - b * quotient;

Because the quotient is also needed, doing it that way does actually make some sense.

Test cases

let f =

f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)

console.log(f(2))
console.log(f(50000000002))
console.log(f(1000000))

\$\endgroup\$
  • \$\begingroup\$ You only need 64 bit flooring in the last occurence so you can replace the other ones with 0|x/y and remove the declaration \$\endgroup\$ – Oki Jul 4 '17 at 11:19
5
\$\begingroup\$

C++11 (GCC/Clang, Linux), 104 102 bytes

using T=__int128_t;T m=1e11+3;T f(T a,T r=1,T n=m-2){return n?f(a*a-a*a/m*m,n&1?r*a-r*a/m*m:r,n/2):r;}

https://ideone.com/gp41rW

Ungolfed, based on Euler's theorem and binary exponentation.

using T=__int128_t;
T m=1e11+3;
T f(T a,T r=1,T n=m-2){
    if(n){
        if(n & 1){
            return f(a * a - a * a / m * m, r * a - r * a / m * m, n / 2);
        }
        return f(a * a - a * a / m * m, r, n / 2);
    }
    return r;
}
\$\endgroup\$
  • \$\begingroup\$ ISO C++ only requires long to be at least 32-bit, so it can't necessarily hold 1e11 + 3. It's 32-bit on x86-64 Windows. long is a 64-bit type on x86-64 Linux (and other OSes that use the SystemV ABI), though. So to be fully portable, you'd need to use long long, which is guaranteed to be at least 64-bit since C++11. \$\endgroup\$ – Peter Cordes Jul 4 '17 at 18:21
  • \$\begingroup\$ __int128_t doesn't seem to be standard C++, it seems to be a gcc extension, it would be cool if you'd state this as a language (C++11 + gcc). \$\endgroup\$ – Felix Dombek Jul 4 '17 at 18:38
  • 3
    \$\begingroup\$ This is not supposed to be a C++ experts site, I hoped no one will notice. \$\endgroup\$ – SteelRaven Jul 4 '17 at 18:47
  • \$\begingroup\$ @PeterCordes Code golf doesn't need to be portable or even well-formed, it just needs to work on one implementation. \$\endgroup\$ – aschepler Jul 4 '17 at 22:25
  • 1
    \$\begingroup\$ @aschepler: I know, which is why I said "you would need". I thought it was useful to point out which platform it would/wouldn't work on, in case anyone tried it and ran into trouble. \$\endgroup\$ – Peter Cordes Jul 5 '17 at 5:50
4
\$\begingroup\$

Mathematica, 49 bytes

x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&
\$\endgroup\$
  • \$\begingroup\$ How long does this take to run? \$\endgroup\$ – user9206 Jul 5 '17 at 6:52
  • \$\begingroup\$ Less than 0.001s on my computer (for case 2^40-1) \$\endgroup\$ – Keyu Gan Jul 11 '17 at 8:37
2
\$\begingroup\$

PHP, 71 bytes

for(;($r=bcdiv(bcadd(bcmul(++$i,1e11+3),1),$argn,9))!=$o=$r^0;);echo$o;

Testcases

\$\endgroup\$
1
\$\begingroup\$

Ruby, 58 bytes

Uses isaacg's application of Fermat's little theorem for now while I finish timing the brute-force solution.

->n,x=10**11+3{i=n;11.times{i**=10;i-=i/x*x};i*=n;i-i/x*x}

Current brute force version, which is 47 bytes but might be is too slow:

->n,x=10**11+3{(1..x).find{|i|i*=n;i-i/x*x==1}}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy