CHMOD - Editorial

Yeah same approach. A(i) < =100 was big hint for me :slight_smile:

1 Like

:smiley: 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 :slight_smile:

1 Like

iā€™d got AC and my power function was recursive too :smiley:

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ā€¦ :slight_smile:

so was mine !

@shantanuag Thank you for your inputs on this. :slight_smile:

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 :wink:

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.

@kunal361 thanks for pointing it outā€¦i donā€™t know what i was thinkingā€¦