Here's a funny problem that I've composed for the Russian IOI training camp that's happening now.
Given two numbers a and b in base 31 with at most one million digits each such that a is a multiple of b, find the last k digits (again, in base 31) of a/b, where k is not more than 10000.
This is very similar to a problem on Project Euler, the caveat being the base 31 part. The last k digits of a number n in base 31 are (n mod 31^k). You want ((a/b) mod (31^k)), which is (a mod 31^k) / (b mod 31^k). But (a mod 31^k) is just the last k digits of a, and likewise for (b mod 31^k) and b.
The problem is doing the arithmetic, because converting to base 10 and back could be problematic in the extreme cases. Is the intent of the problem, then, to write a division routine in base 31?
2Abishek: what do you mean by "((a/b) mod (31^k)), which is (a mod 31^k) / (b mod 31^k)"? I don't think that is true. Suppose a=42,b=6,k=1. Then a mod 31^k=11 which is not divisible by b mod 31^k=6.
2Ivan: wow, thanks for the link. I knew it must be a well-known idea :)
Hmnn only bell that rang when reading it is that 31 is prime.
31^k is still a product of primes and we know all its prime factors.
so calculating (a%(31^k) / v%(31^k) ) % (31^k) should be possible using that one theorem I don't remember exactly.
So, I open wikipedia and it seems we'll first have to computer (1/b)%(31^k) like this: http://en.wikipedia.org/wiki/Euclidean_algorithm#Multiplicative_inverses_and_the_RSA_algorithm
still, implementing the Euclidean algorithm on big numbers keeping efficiency sounds non-trivial. Still not sure if that's the way.
You can only do that when b is not divisible by 31, but after you account for that, your solution should work, but I'm not sure if it will work fast enough.
The intended solution, however, is simpler than extended Euclidean algorithm :)
cool problem, one hour and i can't solve it
ReplyDeleteThis is very similar to a problem on Project Euler, the caveat being the base 31 part. The last k digits of a number n in base 31 are (n mod 31^k). You want ((a/b) mod (31^k)), which is (a mod 31^k) / (b mod 31^k). But (a mod 31^k) is just the last k digits of a, and likewise for (b mod 31^k) and b.
ReplyDeleteThe problem is doing the arithmetic, because converting to base 10 and back could be problematic in the extreme cases. Is the intent of the problem, then, to write a division routine in base 31?
2Abishek: what do you mean by "((a/b) mod (31^k)), which is (a mod 31^k) / (b mod 31^k)"? I don't think that is true. Suppose a=42,b=6,k=1. Then a mod 31^k=11 which is not divisible by b mod 31^k=6.
ReplyDelete2Ivan: wow, thanks for the link. I knew it must be a well-known idea :)
Oops, that property only holds for multiplication.
ReplyDeleteHmnn only bell that rang when reading it is that 31 is prime.
ReplyDelete31^k is still a product of primes and we know all its prime factors.
so calculating (a%(31^k) / v%(31^k) ) % (31^k) should be possible using that one theorem I don't remember exactly.
So, I open wikipedia and it seems we'll first have to computer (1/b)%(31^k) like this: http://en.wikipedia.org/wiki/Euclidean_algorithm#Multiplicative_inverses_and_the_RSA_algorithm
still, implementing the Euclidean algorithm on big numbers keeping efficiency sounds non-trivial. Still not sure if that's the way.
2vexorian:
ReplyDeleteYou can only do that when b is not divisible by 31, but after you account for that, your solution should work, but I'm not sure if it will work fast enough.
The intended solution, however, is simpler than extended Euclidean algorithm :)
This comment has been removed by the author.
ReplyDeleteIt is easy.
ReplyDeleteif we use Garnet's scheme and make some precalculation, then we have next algo:
1. a = (a_1 a_2 ... a_n)
b = (b_1 b_2 ... b_m)
2. a * b ^ -1 mod 31 = Suma(i = 1,n; a_i * 31^(n - i) ) * Suma(i = 1,n; b_i * 31 ^ (n - i)) ^ -1 mod 31 = 31 ^ (k1 - k2) * Suma(i = 1,n; a_i * 31^(n - i - k1) ) * Suma(i = 1,n; b_i * 31 ^ (n - i - k2)) ^ -1 mod 31.
We can easy compute both Suma(...) mod 31 (as precalculated) and then multiply to 31 ^ (k1 - k2). if b | a, then k1 - k2 >= 0.
3. a = (a_1 a_2 ... a_(n-1))
b = (b_1 b_2 ... b_m) * 31
4. goto step 2.
The Complexity is O(n * log(31)) = O(n). :).
Are available more problems of the training camp?
ReplyDeletehey petr plz help him out http://kodejunky.blogspot.com/2009/10/humble-beginning.html
ReplyDelete