PROBLEM LINK:
Author: Pavel Sheftelevich
Tester: Roman Rubanenko
Editorialist: Paweł Kacprzak
DIFFICULTY:
Easy
PREREQUISITES:
Math, Big-num
PROBLEM:
For each test case you are given a number m and an expression which contains only numbers multiplications and exponentiations. Your task is to find the value of the expression modulo m
QUICK EXPLANATION:
Parse the expression and calculate it using big num representation and fast exponentiation.
EXPLANATION:
EXPECTED SOLUTION:
If we are able to handle 3 operations: multiplication, exponentiation and modulo calculation, we can solve the problem easily after parsing the input first. Since input numbers can be very large, this is not straightforward and I’ll show how to implement these 3 operations step by step:
-
Calculating modulo. Let assume that we have to calculate A M. In this problem M is always < 10^8 so we can store it as 64-bit integer. Let d<sub>k-1</sub>, d<sub>k-2</sub>, ..., d<sub>0</sub> be the digits of A from left to right. Then A = 10^(k-1) * d<sub>k-1</sub> + 10^(k-2) * d<sub>k-2</sub> + ... + d<sub>0</sub> and based on this fact, we can write A M as (10^(k-1) * dk-1) M + (10^(k-2) * d<sub>k-2</sub>) M + … + d0 % M which can be easily computed using Horner’s method - please check the author’s solution for details.
-
Exponentiation. Let assume that we have to calculate A^B, where A and B can be arbitrary long numbers. First we can calculate reduce A to A^M because (A^B) % M = ((A%M)^B) % M. So now we are raising a number A < 10^8 to an arbitrary long exponent. Let B = 10^(k-1) * dk-1 + 10^(k-2) * dk-2 + … + d0 where di is the i-th rightmost digit of B. Then A^B = A^(10^(k-1) * dk-1 + 10^(k-2) * dk-2 + … + d0) which can be written as A^(10^(k-1) * dk-1) * A^(10^(k-2) * dk-2) * … * A^d0 and you can again use the Horner’s method to compute it - please check the author’s solution for details.
-
Multiplication of two numbers A, B < 10^18 modulo MOD < 10^18. The result of this operation may not fit into 64-bit integer, so we have to be smart here. You can use the same idea as in the fast exponentiation algorithm here, please check this function from author’s code:
long long MOD;
long long mult(long long A, long long B)
{
if ( B == 0 ) return 0;
long long u = mult(A, B/2);
long long res;
if ( B%2 == 0 )
res = u + u;
else
res = u + u + A;
while ( res >= MOD ) res -= MOD;
return res;
}
SOLUTION USING BIG NUMS:
Since numbers in the statement can be very large and m can be big also, this problem is very easier to code in a language which has implemented a big number representation. For example Java or Python is a really good choice here. If you are planing to write the solution in a language which doesn’t support big numbers, you have to implement it on your own along with operation of multiplication, fast exponentiation (which is done by multiplication) and modulo calculation. The bottom line is that you have a strong advantage here if you are using a language which supports big numbers or you have an implementation of it prepared before the contest.
I will focus now on the implementation, because if you do it fast and smart, you can benefit huge from it.
First things first, we have to parse the input statement, because it is given as a string of numbers and operands. If you are familiar with regular expressions, you are in a pole position here. Let change two start representing exponentiation to ^ symbol duo to formatting issues in this editor only for editorial purposes. If we divide the statement x1^y1 * x2^y 2 * … * xn^yn into pairs of numbers (x1, y1), (x2, y2), …, (xn, yn) we can first compute the result of exponentiation for each pair and then multiply these intermediate results. So let’s split the input statement just into consecutive numbers! Then we can get two such numbers, do the exponentiation on them and multiply the current result by the result of this exponentiation - remember that all operations have to be calculated modulo m.
If you are using python or another language with regular expressions built in, you can split the input statement s in consecutive numbers using the below regular expression:
re.split(r'[^0-9]+', s)
where s is the input string and re is the standard regular expression module
In python there is a built in fast exponentiation functions which can also calculate the result modulo given number. To compute (a^b) % c just run mod(a, b, c). I encourage you to use it, because it is really fast and very well implemented.
If you want to know how to do fast exponentiation on your own, please check this link. One important note is that for big exponents, a resursive exponentiation of it will give you Runtime Error duo to stack overflow. You should implement it iteratively.
Since my python solution in quite short, you can see the full code below:
import re
t = int(raw_input())
for i in xrange(t):
m, s = raw_input().strip().split()
m = long(m)
s = s.strip()
a = re.split(r'[^0-9]+', s)
res = 1
for i in xrange(0, len(a), 2):
res = (res * pow(long(a[i]), long(a[i + 1]), m)) % m
print res
ALTERNATIVE SOLUTIONS:
For the first subtask, you don’t have to use big numbers at all since numbers in the expression are digits and m is small enough. For the second subtask, every result of an exponentiation can be keeped small when calculated modulo m, because m < 10^9 and this allows you to do multiplication in the statement in 64-bit integers because a * b, for a, b < 10^9 fits 64-bit integer.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
another of doubts was how was it possible to have xi and yi of the order 10^999 or so; since the string length was restricted to a lesser value (10^4)?