LCH15JEF - Editorial

PROBLEM LINK:

Practice
Contest

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:

  1. 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.

  2. 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.

  3. 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.

RELATED PROBLEMS:

3 Likes

These kind of programs pose a huge advantage to JAVA / PYTH users.

Luckily , I code in Java and so I could use BigInteger and get a 100 easily.

But,such programs are not advisable for contests like LunchTime where one

expects high standard algorithmic programs rather than just implementation.

6 Likes

@pkacprzak I implemented the same thing as your editorial but I was awarded only partial points.
What part have I missed?
Solution link here.

Thanks,

Regards, Ankit

TIL Python has fast modular exponentiation. Thanks!

Worst problem of all time. This type of problem (boring, unoriginal and made for Python/Java) is useless in a contest of this kind. A language should not be favored by a problem.

4 Likes

I did it in Python as these problem are only language oriented / implementation oriented

import sys 
f = sys.stdin
T = int(f.readline())
while T:
 
	M,S = [str(x) for x in f.readline().split()]
	N = len(S)
	i = 0
	ans = 1 
	M = int(M)
	while i '9' or S[i] < '0') :
			i += 1 
		op1 = 0 
		while i < N and (S[i] <= '9' and S[i] >= '0') : 	
			op1 = op1 * 10 + (int(S[i])-int('0'))
			i += 1
 
		while i < N and (S[i] > '9' or S[i] < '0') :
			i += 1 
		op2 = 0 
		while i < N and (S[i] <= '9' and S[i] >= '0') : 	
			op2 = op2 * 10 + (int(S[i])-int('0'))		
			i += 1 
		ans = ans * pow(op1,op2,M)
		ans %= M
	print ans 		 
	T -= 1 

Java (and even Python maybe) will be available in the upcoming IOIs, so I don’t think this problem is completely useless since one should keep in mind that different languages, which I consider as weapons, have different advantages.

Ask any ACM ICPC team, there is always someone who could program in Java because it offers BigDecimal and BigInteger.

@pkacprzak I am sorry for that comment. I wasn’t paying attention to whose solution it is.

@ankitdhall I see that you are using int64_t as you big, but int64_t is the 64-bit integer which is not enough for this problem. You have to be able to handle numbers consisting of 9998 digits.

1 Like

@gdisastery1 If you see 10 more problems like this, you could get a WRONG impression that Java/Python are better because there are prewritten classes for big numbers, for example.

@alexvaleanu If you are a beginner, you might get this wrong impression. So you are implying C++ is better than Java/Python? Even though it is the most preferred language in competitive programming (I also use C++ mainly), it is not the best - it really depends on the problem.

thanks for the looking into my code! :slight_smile: 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)?
Thanks for your time :slight_smile:

@gdisastery1 This is the point that I am trying to prove. I am not saying which language is better. It does not matter. A language should not be favored by a problem.

Since there is a big discussion on this problem, I’ll give my view on it:

@alexvaleanu This python solution is mine and I wrote it for editorial purposes. I also code 99% of problems in C++, but I know that there are problems for which there are better languages and this is one of them.

Here is the important note

Are you complaining that you code in C++ and this problem is the worst of all time? Think different. If there is an user who codes in Python mainly and he has to implement a very complicated data structure in order to solve a problem, should he complain that this is the worst problem of all time because he cannot code it in Python? Be versatile, I am not the author of the problem, but this is a programming competition and not C++ contest.

10 Likes

Again, I am truly for my mistake. If a Python user should code a very complicated data structure, a C++ user should too. Problems should not be about different aspects of programming languages.

@alexvaleanu I mean, that for python coder, coding a complicated data structure is usually out of their range

@alexvaleanu There are always two sides of a problem in a PROGRAMMING CONTEST - first the theoretical solution - with pseudocode maybe, and second the implementation. If you are saying the problems should not be dependent on the language, each problems would only have the first part - and we would all be writing pseudocode or explaining the solution theoretically. Boring, isn’t it?

If you are picking the wrong tool for the wrong problem, then it’s your fault for coding too long. It’s like cutting a cucumber with a hammer.

3 Likes

@ankitdhall, just notice that 10^9997 has 9998 digits and a string of length 10^4 can have 10000 digits :wink:

I implemented the biginteger using strings in c++ and did the problem the same way as in the editorial . But it gives me a TLE . solution link

Looks like I should learn java