1
You're given two numbers a and b in base 31 numeral system and number k with no more than 10000 decimal digits. It is known that b is divisor of a. The task is to find last k 31-based-digits of quotient a/b.
The solution with fastest proved asymptotics in length of max(a,b) wins. I'll put a bound of 10^5 on length of a and b.
Test example:
INPUT: a = IBCJ, b = OG, k = 5
OUTPUT: 000N7
Igor
Posted 2016-02-13T20:51:52.227
Reputation: 111
1Welcome to Programming Puzzles & Code Golf! This site is for programming contests and challenges, not general programming questions. Yours might be on-topic on [programmers.se] or [cs.se], but be sure to read their help centers to make sure your question is high in quality and on-topic there. Thanks! – Doorknob – 2016-02-13T20:53:13.313
@Doorknob I've changed the statement so that it should satsify the rules. – Igor – 2016-02-13T20:56:20.523
1
"There isn't just one input so one may be O(n) in a but O(n^2) in k, and another solution may be the other way around. Which one wins?" - @trichoplax. As it stands, I don't think that the winning criteria is clear enough. Take a look at the tag wiki too for info on the fastest-algorithm tag.
– Liam – 2016-02-13T21:21:31.237