×

# LCH15JEF - Editorial

Author: Pavel Sheftelevich
Tester: Roman Rubanenko
Editorialist: Paweł Kacprzak

Easy

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.

# 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 dk-1, dk-2, ..., d0 be the digits of A from left to right. Then A = 10^(k-1) * dk-1 + 10^(k-2) * dk-2 + ... + d0 and based on this fact, we can write A % M as (10^(k-1) * dk-1) % M + (10^(k-2) * dk-2) % 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:

This question is marked "community wiki".

75485097
accept rate: 12%

TIL Python has fast modular exponentiation. Thanks!

(25 Jan '15, 14:38)

Looks like I should learn java

(25 Jan '15, 15:53) 3★

can anyone explain the author's solution? I have no idea how, exponetiation happened in it...

(25 Jan '15, 19:40)
(25 Jan '15, 19:57) 3★

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.

75485097
accept rate: 12%

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.

(25 Jan '15, 15:07)

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

(25 Jan '15, 15:11)
3

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

(25 Jan '15, 15:13)
 5 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. answered 25 Jan '15, 14:35 883●1●4●22 accept rate: 9% 1 It was a good problem and can be coded easily in C++ if one remembers basic arithmetic operations and the logic behind them. I did it easily. (02 Feb '15, 14:23)
 4 To all who thinks that this problem is just about parsing, implementation and programming languages(especially as @alexvaleanu) Author's solution implemented in C++ and doesn't require any big numbers arithmetic. Editorial will be updated soon. Now you can have a look at author's solution. Sorry for the situation with many solutions easily passed using Python or Java, that wasn't supposed(but it's programming contest and I think it's ok to use advantages of the languages though it wasn't planned). Also I think you should at first think about possible alternative algorithm ideas(by the way not absolutely obvious) before writing: "Worst problem of all time" answered 25 Jan '15, 16:14 69●3 accept rate: 0% 1 Nice problem, I guess it's unfortunate that it could be solved so easily with other languages. Why doesn't the editorial describe this solution instead of talking about the obvious brute force bignum algorithm? The reason everyone is raging here is because it looks like the official and expected solution is to use Python/Java because that's the only solution described in the editorial. If your solution had been posted as the editorial then I doubt as many people would have complained. (25 Jan '15, 19:44) superty3★
 1 Please explain the exponentiation part of the author's solution. I believe this is a very useful problem for C,C++ programmers. answered 25 Jan '15, 19:49 11 accept rate: 0% (25 Jan '15, 19:55) damn_me3★
 0 @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 answered 25 Jan '15, 14:37 21●2 accept rate: 0% 1 @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. (25 Jan '15, 14:52) thanks for the looking into my code! :) 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 :) (25 Jan '15, 14:57) @ankitdhall, just notice that 10^9997 has 9998 digits and a string of length 10^4 can have 10000 digits ;) (25 Jan '15, 15:16)
 0 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. answered 25 Jan '15, 14:41 559●1●3●12 accept rate: 7% 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. (25 Jan '15, 14:49) @pkacprzak I am sorry for that comment. I wasn't paying attention to whose solution it is. (25 Jan '15, 14:51) @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. (25 Jan '15, 14:53) @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. (25 Jan '15, 14:56) @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. (25 Jan '15, 15:01)
 0 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  answered 25 Jan '15, 14:46 1.7k●1●17●30 accept rate: 11%
 0 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 answered 25 Jan '15, 15:30 1 accept rate: 0% same thing happened to me. c++ bigint code gets TLE (25 Jan '15, 15:53)
 0 http://www.codechef.com/viewsolution/5993673 . Any ideas why this solution got NZEC ? answered 25 Jan '15, 16:36 57●1●5 accept rate: 0%
 0 The difficulty says "To be updated soon". Isn't it decided during problem setting?? answered 25 Jan '15, 16:50 893●2●11●35 accept rate: 10% It is updated now, but in general deciding a difficulty after the contests is better, because a number of contestants who solve it correctly affect the level of difficulty. For example, there can be an unexpected method of solving it which comes up during a contest. (26 Jan '15, 07:49)
 0 Although I missed the contest, I was trying to solve the problems! When I solved this problem in python, the following code worked perfectly for me: T = int(raw_input()) for t in range(T): M, S = map(str, raw_input().split())  M = int(M) S = eval(S) print S%M However, when I checked a few solutions, they were way too long codes!!! Is my code wrong? answered 25 Jan '15, 17:07 2★mitra95 1 accept rate: 0% Your code will only work for the first subtask. IT will timeout for the rest. (25 Jan '15, 17:45) It's still possible to write a solution quite a bit shorter than the ones most contestants have done. http://www.codechef.com/viewsolution/5994630 (25 Jan '15, 20:24) superty3★
 0 author's solution is giving wrong answer consider this input: 1 10000 2x3x4x5 answer should be =120 author's answer = 1 answered 25 Jan '15, 20:20 1●1 accept rate: 0% String cannot be input this manner. Its of the format (a1)(a2)(a3)....an where each ai is of the form bi**bj. (25 Jan '15, 20:23) damn_me3★
 0 @pavel1996 when i use author solution and replace in solve() for (int i=0;i
 0 while Calculating modulo of A % M , M < 10^8 A = 10^(k-1) * dk-1 + 10^(k-2) * dk-2 + ... + d0 A % M = (10^(k-1) * dk-1) % M + (10^(k-2) * dk-2) % M ` how are we handling for k > 30 ? answered 02 Feb '15, 03:22 2★bicepjai 11 accept rate: 0%
 0 http://www.codechef.com/viewsolution/6589294 This is fetching only 70 points. It's probably something got to do with overflow but I can't figure out what. What am I missing? answered 28 Mar '15, 20:51 2★sandy999 391●1●16●38 accept rate: 10%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×1,220
×849
×87
×22

question asked: 25 Jan '15, 14:32

question was seen: 4,749 times

last updated: 03 Apr '15, 20:53