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