Codersbit Problem

How to calculate (x^(y^z)) % 1000000007 ?

There is something called Euler totient function using it you can solve it like:
x^(y^z) = x^( (y^z)%PHI(M) ) % M
where PHI(M) is the value for totient function for M. If M is prime then PHI(M) = M-1
so basically you needed to do:
x^(y^z) = x^( (y^z)%1000000006) % 1000000007
I just calculated value of 2^i % 10e9+6 for the question

6 Likes

Any reason for taking M-1.
Because, No will believe that solution was wrong just because of taking M, not M-1.

Well I already told there is something called Euler totient function which helpful to calculate x^(y^z) since while calculation of y^z you cannot take %M since rule is applicable only for addition,multiplication and subtraction and y^z can overflow so you need to take mod somehow. Read the Application mentioned here :https://cp-algorithms.com/algebra/phi-function.html

There was a question in a Long contest of Codechef that’s why I know about it.

2 Likes

Thankyou !! :innocent:

even if u didn’t know the euler totient function …!!!

This can be done by following intuition …

eg
3^(2^5)=9^(2^4)=81^(2^3) and so on
this can be done in o(n) here n is 5 in the ques n can be upto 10^5 which can easily be done in 1 sec or less.
if u didn’t get ask me again …!!!

Sorry didn’t get you

This might help : https://www.geeksforgeeks.org/find-power-power-mod-prime/

3 Likes

Can’t we Binary Exponentiaton instead?

i did this power 62 at a time but got only partial credit due to TLE.
We have to do this for each i from 1 to n so this is not feasible.

@all_too_well no this can be …see below

as all the prime no have the same power ,so first iterate from 1 to n and multiply all the prime no .
after first pass u will get a single no (say it’s x ( prod of all prime no from 1 to n))
now only task left is (x^(2^k)) which can be done in o(k) and k <= 100000 ,so this will pass without any TLE.

1 Like

Bro can u explain me plz with some example :slight_smile:

Just a query . Does anyone know when is the finals of codersbit is scheduled . did anyone get any email regarding this ?

I emailed them but as expected no response from their side and they have done lots of controversial things like they said they will organize 40 contest i got to give only 1 and my college got 2 contest .2nd contest for those who missed 1st one and they said top 1000 but from different leaderboard how will they select :sweat_smile::sweat_smile:

Everyone got only 1 contest and every college got 1 or 2 contest . But they did not inform anything that’s the problem.

2 Likes