We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I think this coding test is left by the website manager in the forgotten corner. Why do I say this?
First of all, the editorial is not as informative as for others. So I need to really check wikipedia and search for what I could really use.
Secondly, the forum is full of advertisements, perhaps providing virus links. I think all those comments should be removed.
Back to the problem itself, here are some "more detailed" hints from me:
Use the information from the Math StackExchange website. It helps to reduce the test cases you need to try for each number g. To be concrete, instead of trying all the powers from 0 to p-2, you can simply try the numbers , where denotes the ith distince prime factor of p-1. This can significantly reduce the computation load.
when you calcualate the Euler totient function of p-1, you can use the formula: , where denotes the ith distince prime factor of x. This is also known as "the Euler product formula". You can find it in the wikipedia page.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Primitive Problem
You are viewing a single comment's thread. Return to all comments →
I think this coding test is left by the website manager in the forgotten corner. Why do I say this?
First of all, the editorial is not as informative as for others. So I need to really check wikipedia and search for what I could really use.
Secondly, the forum is full of advertisements, perhaps providing virus links. I think all those comments should be removed.
Back to the problem itself, here are some "more detailed" hints from me:
Use the information from the Math StackExchange website. It helps to reduce the test cases you need to try for each number g. To be concrete, instead of trying all the powers from 0 to p-2, you can simply try the numbers , where denotes the ith distince prime factor of p-1. This can significantly reduce the computation load.
when you calcualate the Euler totient function of p-1, you can use the formula: , where denotes the ith distince prime factor of x. This is also known as "the Euler product formula". You can find it in the wikipedia page.