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.
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.
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:
Alternate Writer: Labib Md Rashid