PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:Easy PREREQUISITES:Math, Bignum 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:
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 x_{1}^y_{1} * x_{2}^y _{2} * ... * x_{n}^y_{n} into pairs of numbers (x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n}) 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'[^09]+', 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'[^09]+', 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 64bit integers because a * b, for a, b < 10^9 fits 64bit integer. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 25 Jan '15, 14:32

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 noteAre 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. answered 25 Jan '15, 15:02
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)

To all who thinks that this problem is just about parsing, implementation and programming languages(especially as @alexvaleanu) answered 25 Jan '15, 16:14
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)

@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
1
@ankitdhall I see that you are using int64_t as you big, but int64_t is the 64bit 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)

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
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)

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<n: while="" i="" <="" n="" and="" (s[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

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

http://www.codechef.com/viewsolution/5993673 . Any ideas why this solution got NZEC ? answered 25 Jan '15, 16:36

@pavel1996 when i use author solution and replace in solve()
with for (int i=0; s[i] != '\0'; i++) i got WA. can you tell me why?
link
This answer is marked "community wiki".
answered 27 Jan '15, 22:30

while Calculating modulo of
how are we handling for k > 30 ? answered 02 Feb '15, 03:22

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

TIL Python has fast modular exponentiation. Thanks!
Looks like I should learn java
can anyone explain the author's solution? I have no idea how, exponetiation happened in it...
Refer this: http://discuss.codechef.com/questions/62764/exponentiationlch15jef