WA in MATBREAK in april cook-off

problem link: https://www.codechef.com/COOK117B/problems/MATBREAK

solution link: https://www.codechef.com/viewsolution/32090721

I tried in 4 or 5 cases and it is giving expected output only, cant figure out where i am going wrong

for _ in range(int(input())):
n,a = map(int, input().split())
m, result, Pi =	int(10e8)+7, 0, 1

for i in range(1, n+1):
	Pi = pow((a), (2*i)-1, m)
	result = (result + Pi) % m
	a = (a * Pi) % m 


Here’s my solution

i applied the same logic but got WA

I guess here you can’t use power function , i used modular exponentiation.

1 Like

This solution was accepted or not in contest?

Yes you are right modular exponentition is to be used here is my solution CodeChef: Practical coding for everyone

actually in python their is no overflow issue even for very huge numbers.
so you can use simple power instead of modular exponentiation.

yes it worked small error caused so much rank loss

Yes It was

Try optimising your code

Does a solution without modular power work?

In my first attempt it game me TLE and I thought looping over such big numbers was taking too much time so I tried to find/derive general formula for it and in that process It took me 1 hour and then I realised it was just a missing modulo that was giving TLE. [


I wasted 1 hour for such a silly mistake.

How yr…we all applied the same logic… I guess.

As said by @iamsv345 “there is no overflow issue for very huge numbers in python but not in case of c/c++” therefore you have to use modular exponentiation to avoid error.

@anshulbansal53 is right. Python supports big integers. C++ and C doesn’t. So logic might be same in both languages, but you need to add modular arithmetic in C++'s case.I wasted 3 hours on implementing it. Still it kept showing WA. Finally I got help in discussion thread.