Idea:
We can solve this problem applying Euler’s theorem and dynamic programming. If we understand the theorem clearly then it becomes very easy to solve the problem.

Please check this links to learn necessary things to solve this problem.
Euler's Theorem
How to calculate (a^(b^(c^d)))%mod using Euler’s Theorem
Euler's Phi Function

First we need to pre calculate all the Mod values using Euler’s Phi function. Then to calculate the attractiveness of any node we can solve it recursively expanding the Euler’s theorem. We also need to apply dynamic programming here. And there will be two state in DP.

  1. Which node we are currently in.
  2. The distance between the current node and the node whose attractive value we are calculating.

Then for each node we can solve recursively and update the result using the Phi values as Mod values.

Complexity: O(N*K)

Judge Solution: Solution Link

Alternate Writer: Labib Md Rashid

Statistics

72% Solution Ratio
imranziadEarliest, Jan '17
mahabub.tweetFastest, 0.2s
SilentGLightest, 8.4 MB
mpnri2Shortest, 1457B
Toph uses cookies. By continuing you agree to our Cookie Policy.