Problem p03196 (python)

Fixed submission:
#CADDi2018 C
'''
問題
N個の自然数の積がPであるとき,それらの最大公約数としてありうるものの最大値を求めよ
ただしNとPはともに1以上10**12以下

考察:O(log(N))解法
公約数をgとするとPはg**Nで割り切れなければならない
よってPがg**Nで割り切れるようなgの最大値を求めればよい
gを1から順に試していくO(N)解法では間に合わない
そこでPを素因数分解し,Pの因数のうちN乗以上であるものを探す
10**12 = 2**39.8... なのでPの因数はたかだか39乗である
10**12 = 3**25.1...
10**12 = 4**19.9...
10**12 = 5**17.1...
10**12 = 6**15.4...
10**12 = 7**14.1...
10**12 = 8**13.2...
10**12 = 9**12.5...
N=1のときはg=P
N=2のときはg<=10**6
N=3のときはg<=10**4
N=4のときはg<=1000
N=5のときはg<=251
N=6のときはg<=100
N=7のときはg<=51
N=8のときはg<=31
N=9のときはg<=21
N=10のときはg<=15
N=11のときはg<=12
N>=12のときはg=1,2,3,4,5,6,7,8,9,10のいずれか
N>=13のときはg=1,2,3,4,5,6,7,8のいずれか
N>=14のときはg=1,2,3,4,5,6,7のいずれか
N>=15のときはg=1,2,3,4,5,6のいずれか
N>=16のときはg=1,2,3,4,5のいずれか
N>=18のときはg=1,2,3,4のいずれか
N>=20のときはg=1,2,3のいずれか
N>=26のときはg=1,2のいずれか
N>=40のときはg=1
'''
N,P=map(int,input().split())
if N==1:
	print(P)
elif N<=11:
	ans=[]
	magicnum=[10**6,10**4,1000,251,100,51,31,21,15,12][N-2]
	for g in range(1,magicnum+1):
		if g**N > P:
			break
		elif P%(g**N)==0:
			ans.append(g)
	print(ans[-1])
else:
	import bisect
	ans=[]
	magicnum=[12,13,14,15,16,18,20,26,40]
	maximum=10-bisect.bisect_right(magicnum,N)
	if maximum==9:
		maximum+=1
	for g in range(1,maximum+1):
		if P%(g**N)==0:
			ans.append(g)
	print(ans[-1])

Buggy submission (verdict: Runtime Error):
#CADDi2018 C
'''
問題
N個の自然数の積がPであるとき,それらの最大公約数としてありうるものの最大値を求めよ
ただしNとPはともに1以上10**12以下

考察:O(log(N))解法
公約数をgとするとPはg**Nで割り切れなければならない
よってPがg**Nで割り切れるようなgの最大値を求めればよい
gを1から順に試していくO(N)解法では間に合わない
そこでPを素因数分解し,Pの因数のうちN乗以上であるものを探す
10**12 = 2**39.8... なのでPの因数はたかだか39乗である
10**12 = 3**25.1...
10**12 = 4**19.9...
10**12 = 5**17.1...
10**12 = 6**15.4...
10**12 = 7**14.1...
10**12 = 8**13.2...
10**12 = 9**12.5...
N=1のときはg=P
N=2のときはg<=10**6
N=3のときはg<=10**4
N=4のときはg<=1000
N=5のときはg<=251
N=6のときはg<=100
N=7のときはg<=51
N=8のときはg<=31
N=9のときはg<=21
N=10のときはg<=15
N=11のときはg<=12
N>=12のときはg=1,2,3,4,5,6,7,8,9,10のいずれか
N>=13のときはg=1,2,3,4,5,6,7,8のいずれか
N>=14のときはg=1,2,3,4,5,6,7のいずれか
N>=15のときはg=1,2,3,4,5,6のいずれか
N>=16のときはg=1,2,3,4,5のいずれか
N>=18のときはg=1,2,3,4のいずれか
N>=20のときはg=1,2,3のいずれか
N>=26のときはg=1,2のいずれか
N>=40のときはg=1
'''
N,P=map(int,input().split())
if N==1:
	print(P)
elif N<=11:
	ans=[]
	magicnum=[10**6,10**4,1000,251,100,51,31,21,15,12][N-2]
	for g in range(1,magicnum):
		if g**N > P:
			break
		elif P%(g**N)==0:
			ans.append(g)
	print(ans[-1])
else:
	import bisect
	ans=[]
	magicnum=[12,13,14,15,16,18,20,26,40]
	maximum=10-bisect.bisect_right(magicnum,N)
	if maximum==9:
		maximum+=1
	for g in range(1,maximum):
		if P%(g**N)==0:
			ans.append(g)
	print(ans[-1])

Buggy submission (verdict: Runtime Error):
#CADDi2018 C
'''
問題
N個の自然数の積がPであるとき,それらの最大公約数としてありうるものの最大値を求めよ
ただしNとPはともに1以上10**12以下

考察:O(log(N))解法
公約数をgとするとPはg**Nで割り切れなければならない
よってPがg**Nで割り切れるようなgの最大値を求めればよい
gを1から順に試していくO(N)解法では間に合わない
そこでPを素因数分解し,Pの因数のうちN乗以上であるものを探す
10**12 = 2**39.8... なのでPの因数はたかだか39乗である
10**12 = 3**25.1...
10**12 = 4**19.9...
10**12 = 5**17.1...
10**12 = 6**15.4...
10**12 = 7**14.1...
10**12 = 8**13.2...
10**12 = 9**12.5...
N=1のときはg=P
N=2のときはg<=10**6
N=3のときはg<=10**4
N=4のときはg<=1000
N=5のときはg<=251
N=6のときはg<=100
N=7のときはg<=51
N=8のときはg<=31
N=9のときはg<=21
N=10のときはg<=15
N=11のときはg<=12
N>=12のときはg=1,2,3,4,5,6,7,8,9,10のいずれか
N>=13のときはg=1,2,3,4,5,6,7,8,9のいずれか
N>=14のときはg=1,2,3,4,5,6,7,8のいずれか
N>=15のときはg=1,2,3,4,5,6,7のいずれか
N>=16のときはg=1,2,3,4,5,6のいずれか
N>=18のときはg=1,2,3,4,5のいずれか
N>=19のときはg=1,2,3,4のいずれか
N>=20のときはg=1,2,3のいずれか
N>=26のときはg=1,2のいずれか
N>=40のときはg=1
'''
N,P=map(int,input().split())
if N==1:
	print(P)
elif N<=11:
	ans=[]
	magicnum=[10**6,10**4,1000,251,100,51,31,21,15,12][N-2]
	for g in range(1,magicnum):
		if g**N > P:
			break
		elif P%(g**N)==0:
			ans.append(g)
	print(ans[-1])
else:
	import bisect
	ans=[]
	magicnum=[12,13,14,15,16,18,19,20,26,40]
	maximum=11-bisect.bisect_right(magicnum,N)
	for g in range(1,maximum):
		if P%(g**N)==0:
			ans.append(g)
	print(ans[-1])