WA in MATBREAK in april cook-off

general
1

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

2 
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 

print(result)

Here’s my solution

3

i applied the same logic but got WA

4

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

1 Like
5

This solution was accepted or not in contest?

6

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

7

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

8

yes it worked small error caused so much rank loss

9

Yes It was

11

Try optimising your code

12

Does a solution without modular power work?

13

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

:man_facepalming:

I wasted 1 hour for such a silly mistake.

14

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

15

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.

16

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