### 1997 Woburn Computer Programming Challenge

## 2. Power of Cryptography

Current work in cryptography involves (among other things) computing large prime numbers and computing powers of numbers modulo these large primes. Work in this area has resulted in the practical use of result from number theory and other branches of mathematics once considered to be only of theoretical interest. This problem involves the efficient calculation of integer roots of numbers.

Given an integer *n* ≥ 1 and an integer *p* ≥ 1 you are to write
a program that determines the *n*th root of *p* — it is guaranteed
that *p* is the *n*th power of some **integer** *k*, i.e.
*p*=*k ^{n}* for some integer k; this is the
integer you are to find.

### Input

The first line of the input is M, the number of test cases to consider.The input consists of M pairs of numbers

*n*and

*p*with each number on a line by itself. For all of these pairs, 1 ≤

*n*≤ 200, 1 ≤

*p*≤ 10

^{101}and there exists an integer

*k*, 1 ≤

*k*≤ 10

^{101}such that

*k ^{n}*=

*p.*

### Output

For each set of values for*n*and

*p*output the value of

*k.*

### Sample Input

3 2 16 3 27 7 4357186184021382204544

### Sample Output

4 3 1234

All Submissions

Best Solutions

**Point Value:** 20

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Sep 28, 2008

**Languages Allowed:**

C++03, PAS, C, ASM, C#, C++11

## Comments (Search)

Foundationon Jul 13, 2009 - 10:29:12 pm UTC Wow...At least one gains programming stamina from overexertion...

bleung91on Apr 07, 2009 - 2:10:04 am UTC Partial Pointsbbi5291on Apr 07, 2009 - 2:12:13 am UTC Re: Partial PointsAll but one (or was it two) of the test cases require essentially no effort to solve. Just giving partial points for them would be too much.

Bobon Jan 01, 2009 - 9:00:55 pm UTC Hints - PLEASE????hansonw1on Jan 01, 2009 - 9:57:38 pm UTC Re: Hints - PLEASE????You have to find a way to multiply numbers of any length.

Try doing "A plus B 2" first.

Bobon Jan 01, 2009 - 8:13:59 pm UTC is there an antilog "function" in pascalbbi5291on Jan 01, 2009 - 8:29:34 pm UTC Re: is there an antilog "function" in pascal^{x}. However, using logs/antilogs no longer works for this problem...Bobon Jan 01, 2009 - 8:38:23 pm UTC Re: Re: is there an antilog "function" in pascalCan you make it 15 partial points instead??

hansonw1on Jan 01, 2009 - 8:50:07 pm UTC Re: Re: is there an antilog "function" in pascalThe answer for the last case won't fit in real or even extended.

bbi5291on Jan 01, 2009 - 7:25:18 pm UTC Test data updated^{101}.