Yeah same approach. A(i) < =100 was big hint for me 
1 Like
Right! Right!
A(i) ā¤ 100 was a hint for many (including me). But for me, the idea of prime numbers didnāt click before there were a few TLEs.
@sandeepandey Thank you for sharing!
@tijoforyou same story here. Apart from the fact that A(i) ā¤ 100 was a hint i figured out at starting
1 Like
iād got AC and my power function was recursive too
Segmented Trees ? Why do you need that in this ?
Using Segment tree was my second approach as storing product of numbers in a product array table was my first approach but I was getting SIGFPE and then latter on WA on both the approaches.
What I was thinking is the highest value of mod is 10^9 and during calculation of product or formation of segment tree, i was taking mod of 10^9 + 7 in order to maintain in the size in int.
After then I thought perhaps this is not good idea so I implemented big integers in c++, this was my first handshake with big integers in c++, thanks to the problem I learned how to use big integers but still problems was not solved and got TLEās.
Interesting. I used prime numbers in the first go and didnāt even notice that storing freqs of 1-100 could have been an alternative approach. To answer your question, I started solving the problem by looking at the segment products. I noticed that theyāll consists of only primes from 1 to 100 and thatās how I came up with the idea of storing prime frequencies. Thanks for this alternative view!
1 Like
I changed your recursive pr function to iterative one and viola!!! It workedā¦
http://www.codechef.com/viewsolution/2528330
I had this same prob. and I donāt know why recursive is failing in our caseā¦as akrai48 has implemented it recursiveā¦I think we have been doing things that arenāt optimizedā¦Would be grateful if someone throw a light on itā¦ 
so was mine !
there so much bilions in result such that owerflow in even long double : result = k * 1e9 + x ; result <= 1e200,000 so , k <= ~1e20000
But when using log10, the max sum is 10.000 * 2 
this is giving TLE
anyone plz help
If youāre doing a naive D&C, query complexity would be Omega(n).
Your recurrence would be T(n) = 2 * T(n / 2) + Omega(1).
T(n) = Omega(n)
In your program, the line res=(res*power(i,tmp[i],m)); can give an overflow. It should have been res=(res*power(i,tmp[i],m))%m; to avoid overflows.
1 Like
@pushkarmishra : hi,could you please elaborate your idea of solving this problem using Segment Tree ?
āPage Not Foundā when tying to access Setterā Solution
I hate the question where key lies in exploiting the limits.