# Nth Root Of M

Posted: 2 Jan, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### You are given two positive integers N and M. You have to find the Nth root of M i.e. M^(1/N).

##### Note:
``````N'th root of an integer M is a real number, which when raised to the power N gives M as a result.

N'th root of the M should be correct up to 6 decimal places.
``````
##### Input Format:
``````The first line of the input contains an integer T denoting the number of test cases.

The first and only line of each test case consists of two space-separated integers N and M.
``````
##### Output Format:
``````For each test case, print a real number with precision till 6 decimal places that denote the Nth root of M in a separate line.
``````
##### Note:
``````You don't have to print anything, it has already been taken care of. Just Implement the given function.
``````
##### Constraints:
``````1<= T <= 10^3
1<= N <= 300
1<= M <= 10^15

Time Limit: 1 sec.
`````` Approach 1
• Let’s say X is the Nth root of M.
• X = M ^ (1 / N)
• The above equation can be written as follows:
• X ^ N = M
• X ^ N - M = 0
• Let’s assume F(X) = X ^ N - M
• Now we need to find the root of this equation, for which we can use the Newton Raphson method to solve this equation.
• In Newton's Raphson method we start with an initial guess value of X (any random initial value is fine) and iterate through a process that takes us towards the actual solution of the equation.
• Let’s say X(0) is the initial guess value.
• The relationship between the current value of solution value x(k) and the solution of the equation in the next iteration X(K + 1) is as follows:
• X(K + 1) = X(K) - F(X(K)) / F'(X(K)), where F'(X(K)) denotes the value derivative of F(X) at X = X(K).                                    ....(1)
• In the given case F'(X(k)) = N * X(K) ^ N - 1.
• So equation (1) can be written as follows:
• X(K + 1) = X(K) - (X(K) ^ N - M) / (N * X(K) ^ N - 1)
• X(K + 1) = (X(K) * (N * X(K) ^ N - 1) - X(K) ^ N + M) / (N * X(K) ^ N - 1))
• X(K + 1) = (X(K) ^ N * (N - 1) + M) / (N * X(K) ^ N - 1)
• So using the above formula to calculate new possible solution value X. Till the gap between X(K + 1) and X(K) become less than 10-7.
• When this condition is reached we get our required solution.