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


  • 1
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! This site is for programming contests and challenges, not general programming questions. Yours might be on-topic on Software Engineering or Computer Science, but be sure to read their help centers to make sure your question is high in quality and on-topic there. Thanks! \$\endgroup\$
    – Doorknob
    Feb 13, 2016 at 20:53
  • \$\begingroup\$ @Doorknob I've changed the statement so that it should satsify the rules. \$\endgroup\$
    – Igor
    Feb 13, 2016 at 20:56
  • 1
    \$\begingroup\$ "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. \$\endgroup\$
    – Liam
    Feb 13, 2016 at 21:21


Browse other questions tagged or ask your own question.