Problem:


Score : 300 points

Problem Statement

There are N integers a_1, a_2, ..., a_N not less than 1.
The values of a_1, a_2, ..., a_N are not known, but it is known that a_1 \times a_2 \times ... \times a_N = P.

Find the maximum possible greatest common divisor of a_1, a_2, ..., a_N.

Constraints

1 \leq N \leq 10^{12}

1 \leq P \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N P

Output

Print the answer.

Sample Input 1

3 24

Sample Output 1

2

The greatest common divisor would be 2 when, for example, a_1=2, a_2=6 and a_3=2.

Sample Input 2

5 1

Sample Output 2

1

As a_i are positive integers, the only possible case is a_1 = a_2 = a_3 = a_4 = a_5 = 1.

Sample Input 3

1 111

Sample Output 3

111

Sample Input 4

4 972439611840

Sample Output 4

206



Sample input:
3 24


Sample output:
2

Submission status: Accepted

Solution code:
import math
n, p = map(int, input().split())
gcd = 1
f = 2
upper = math.floor(math.pow(p, 1/n))

if n == 1:
  gcd = p
else:
  while True:
    if f > upper:
      break
    fn = f**n
    while p%fn == 0:
      gcd *= f
      p /= fn
    if f == 2:
      f = 3
    else:
      f += 2

print(gcd)

Submission status: Accepted

Solution code:
def main():
    n, p = map(int, input().split())
    x = 1

    for f, c in get_prime_factors(p):
        if c >= n:
            x *= f ** (c // n)

    print(x)

def get_prime_factors(p):
    f = 2

    while f * f <= p:
        c = 0
        while True:
            m, r = divmod(p, f)
            if r != 0:
                break
            c += 1
            p = m

        if c != 0:
            yield f, c

        f += 1

    if p != 1:
        yield p, 1

main()

Submission status: Accepted

Solution code:
N,P=list(map(int,input().split()))

root=P**(1/N)
x=round(root)

for i in range(x):
	if P%((x-i)**N)==0:
		print(x-i)
		break

Submission status: Accepted

Solution code:
def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


N, P = map(int, input().split())
fac = factorize(P)
ans = 1
for i in fac:
    ans *= i[0] ** (i[1] // N)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
import sys
N,P=[int(x) for x in input().split()]
if N==1:
    print(P)
    sys.exit(0)
now = P
d = defaultdict(int)
 
for i in range(2,int(math.sqrt(P))+1):
    while  now%i==0:
        now /= i
        d[i]+=1
ans=1
for k in d:
    if d[k] // N > 0:
        ans *= (k ** (d[k] // N))
print(ans)

Submission status: Accepted

Solution code:
def factorized(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

N, P = map(int, input().split())
ans = 1
for t in factorized(P):
    if t[1] >= N:
        ans *= t[0] ** (t[1] // N)
print(ans)

Submission status: Accepted

Solution code:
def usage():
    c, n = map(int, input().split())
    if c == 1:
        print(n)
        return 0
    ans = 1
    fct = factorize(n)
    for i in range(len(fct)):
        if fct[i][1] >= c:
            ans *= fct[i][0] ** (fct[i][1] // c)
    print(ans)


def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


if __name__ == '__main__':
    usage()

Submission status: Accepted

Solution code:
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

if __name__ == '__main__':
    n, p = (int(x) for x in input().split())
    
    list = prime_factors(p)
    count = 0
    beforeValue = -1
    
    ans = 1
    if (n == 1):
        ans = p
    else :
        for i in range(0, len(list)):
            if (beforeValue == list[i]):
                count += 1
                if (count % n == 0):
                    ans *= list[i]
            else:
                count = 1
                beforeValue = list[i]
    print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
from collections import defaultdict


def get_primes(n):
    primfac = []
    d = 2
    while d * d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
        primfac.append(n)
    return primfac


N, P = list(map(int, input().split()))

primes = get_primes(P)

primes_dict = defaultdict(int)

for i in primes:
    primes_dict[i] += 1

for k, v in primes_dict.items():
    primes_dict[k] = int(v / N)

result = 1
for k, v in primes_dict.items():
    result = result * k ** v

print(result)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())

def prime_factorize(num):
    """
    This function performs prime factorization on the input natural number.
    The result is returned in the form of a dictionary with the prime number as the key
    and its number as the value.
    :param num:
    :return prime_factor: Dictionary with the prime number as the key and its number as the value.
    """
    prime_factor = {}
    i = 2
    while i ** 2 <= num:
        while num % i == 0:
            num //= i
            if i in prime_factor.keys():
                prime_factor[i] += 1
            else:
                prime_factor[i] = 1
        i += 1
    if num > 1:
        prime_factor[num] = 1
    return prime_factor


prime_fac = prime_factorize(p)
counts = []
for k, v in prime_fac.items():
    if v >= n:
        counts.append(k**(v//n))

counts.sort(reverse=True)
#print(prime_fac)
#print(counts)
if len(counts) == 0:
    print(1)
elif n == 1:
    print(p)
else:
    r = 1
    num = 0
    for c in counts:
        if num >= n:
            break
        r *= c
        num += 1
    print(r)

Submission status: Accepted

Solution code:
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

N, P = map(int, input().split())
tmp = [p ** (k//N) for p, k in factorize(P) if k >= N]
gcd = 1
for t in tmp:
    gcd *= t
print(gcd)

Submission status: Accepted

Solution code:
import math
n, p = map(int, input().split())
if n==1:
	print(p)
else:
	ans = 1
	limit = math.ceil(p**(1/n))
	while(limit>1):
		cnt = 0
		a = p
		while(a!=0):
			if a%limit == 0:
				cnt += 1
				a = a // limit
			else:
				break
		if cnt >= n:
			ans = limit
			break
		limit -= 1
	print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def prime_decomposition(n):
  i = 2
  table = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i in table:
        table[i] += 1
      else:
        table[i] = 1
    i += 1
  if n > 1:
      if n in table:
        table[n] += 1
      else:
        table[n] = 1
  return table

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, P] = [int(input_raw[0]),int(input_raw[1])]
    table = prime_decomposition(P)
    x = 1
    for p in table:
        if table[p] >= N:
            x *= (p ** (table[p]/N))
    print x

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from statistics import mean, median,variance,stdev
import sys
import math
import fractions
def j(a):
    if a: print("AC")
    else :print("WA")


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())

#x = ip()                              #入力整数1つ
x,y = (int(i) for i in input().split())      #入力整数横2つ
#x,y,z = (int(i) for i in input().split())    #入力整数横3つ
#n,m,x,y= (int(i) for i in input().split())  #入力整数横4つ
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列

max = 1
ls = int(math.sqrt(y))+1
s = []
if y==1 or x>=y:print(1)
elif x==1:print(y)
else:
    n = y
    for i in range(2,ls):
        if n==1:break
        l=0
        while n%i == 0:
             n = n//i
             l+=1
        s.append([i,l])
    for i in range(len(s)):
        s[i][1]//=x
    num = 1
    for i in range(len(s)):
        if s[i][1]: num*=(pow(s[i][0],s[i][1]))
    print(num)

Submission status: Accepted

Solution code:
import math
N,P=map(int,input().split())
flag=1
count=0
z=[]
if P % 2 == 0:
	while P%2 == 0:
		P = P//2
		count+=1
	z.append([2,count])
for i in range(3,P+1)[::flag]:
	count=0
	if P == 1:
		break
	if i > math.sqrt(P):
		z.append([P,1])
		break
	if P%i == 0:
		while P%i == 0:
			P = P//i
			count += 1
		z.append([i,count])
ans=1

for zz in z:
	if zz[1] >= N:
		ans*=zz[0]**(zz[1]//N)
print(ans)

Submission status: Accepted

Solution code:

N, P = map(int, input().split())


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a


if P==1:
    print(1)
else: 
    fct = factorize(P)
    
    al = []

    for div in divisorize(fct):
        al.append(num(div))

    al.sort()
    al.reverse()

    for i in range(len(al)-1):
        c =0
        tmp = P
        while tmp%al[i] == 0 and al[i]>1:
            c = c+1
            tmp = tmp//al[i]
        if c>=N:
            print(al[i])
            break
    else:
        print(1)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
ans = 0
if N == 1:
    print(P)
elif N >= P or N > 50:
    print(1)

else:
    for i in range(1, int(P**(1/N)+2)):
        if P % i**N == 0:
            ans = i
    print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter
n, p = [int(_) for _ in input().split()]

def isprime_alpha(n):
    if n == 1:
        return True
    elif n == 2:
        return True
    elif n == 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    else:
        for j in range(5, math.ceil(n ** (1/2))+1):
            if n % j == 0:
                return False
        return True

def factor(n, fac_list):
    if isprime_alpha(n):
        fac_list.append(n)
        return fac_list
    else:
        for i in range(2, math.ceil(n ** (1/2))+1):
            if n % i == 0:
                fac_list.append(i)
                return factor(n // i, fac_list)

list = []
list_result = factor(p, list)
counter_dict = Counter(list_result)

result = 1
for key, value in counter_dict.items():
    if value % n != 0:
        value -= value % n
    for j in range(value // n):
        result *= key

print(result)

Submission status: Accepted

Solution code:
N, P = [int(x) for x in input().split()]

import types, math, operator
import numpy as np
from math import sqrt
from collections import Counter
from itertools import product
from functools import reduce
class PrimeUtils:
    @staticmethod
    def _has_numpy():
        g = globals()
        m = g.get('np')
        if m is not None and isinstance(m, types.ModuleType):
            return  m.__name__ == 'numpy'
        return False
    @staticmethod
    def _primes_sieve_pp(n):
        sieve = [True] * (n + 1)
        for i in range(2, int(sqrt(n)) + 1):
            if sieve[i]:
                for j in range(i * i, n + 1, i):
                    sieve[j] = False
        return [i for i, x in enumerate(sieve[2:], 2) if x]
    @staticmethod
    def _primes_sieve_np(n):
        sieve = np.ones(n + 1, np.bool)
        sieve[0] = sieve[1] = False
        for i, v in enumerate(sieve[2:int(sqrt(n)) + 1], 2):
            if v: sieve[i*i::i] = False
        return np.nonzero(sieve)[0]
    @staticmethod
    def _primes_sieve_np_fast(n):
        n += 1
        sieve = np.ones(n//3 + (n%6 == 2), dtype=np.bool)
        check_upper = int(sqrt(n)) // 3
        for i, v in enumerate(sieve[1:check_upper + 1], 1):
            if v:
                k = (3*i + 1) | 1
                sieve[k* k           //3::2*k] = False
                sieve[k*(k-2*(i&1)+4)//3::2*k] = False
        sieve[0] = False
        return np.r_[2,3,((3*np.nonzero(sieve)[0] + 1)|1)]
    @classmethod
    def primes_sieve(cls, n):
        if cls._has_numpy():
            return cls._primes_sieve_np_fast(n)
        else:
            return cls._primes_sieve_pp(n)
    # Prime Factor Decomposition
    @classmethod
    def pfd(cls, n):
        primes = cls.primes_sieve(math.floor(n ** (1/N)))

        factors = []
        cur = n
        for p in primes:
            while True:
                div, rem = divmod(cur, p)
                if rem == 0:
                    factors.append(p)
                    cur = div
                else:
                    break
        # assert(cur == 1)
        return factors
    # List up aliquots
    @classmethod
    def aliquots(cls, n):
        pf = cls.pfd(n)
        pfc = Counter(pf)
        ppv = [[pow(p, i) for i in range(n+1)] for p,n in pfc.items()]
        if not ppv:
            return (1,)
        else:
            return map(lambda x: reduce(operator.imul, x), product(*ppv))

from collections import Counter
import functools, operator, itertools
if N == 1:
    print(P)
else:
    c = Counter(PrimeUtils.pfd(P))
    print(functools.reduce(operator.imul, itertools.chain([1], map(lambda x: x[0] ** (x[1]//N), filter(lambda x: x[1] >= N, c.items())))))

Submission status: Accepted

Solution code:
import collections

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

N,P = (int(i) for i in input().split())

tmp = prime_factors(P)
c = collections.Counter(tmp)

num = 1
for index in c.items():
    if index[1] >= N:
        num = num * (index[0] ** (index[1] // N))

print(num)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
t=int(p**(1/n))
x=1
if n<50:
  for i in range(t+1,0,-1):
    if p%(i**n)==0:
      x=i
      break
  print(x)
else:
  print(1)

Submission status: Accepted

Solution code:
[N,P]=[int(i) for i in input().split()]

ans=1

if(N==1):
	ans=P
else:
	i=2
	while(i*i<=P):	

		count=0
		
		while(P%i==0):
			P=P//i
			count+=1

		ans*=pow(i,count//N)

		i+=1

print(ans)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
ans = 1

if N >= 45:
  print(ans)
elif N == 1:
  print(P)
  

  
else:
  i = 1
  while(i**N <= P):
    if P % (i**N) == 0:
      ans = i
    i += 1
  print(ans)