fork download
copy 
  1. # your code goes here
  2. p2=[]
  3. p3=[]
  4. p5=[]
  5. p7=[]
  6. p11=[]
  7.  
  8. inf=10**18
  9.  
  10. def pre():
  11. 	i=1
  12. 	while i<=inf:
  13. 		p2.append(i)
  14. 		i*=2
  15. 	i=1
  16. 	while i<=inf:
  17. 		p3.append(i)
  18. 		i*=3
  19. 	i=1
  20. 	while i<=inf:
  21. 		p5.append(i)
  22. 		i*=5
  23. 	i=1
  24. 	while i<=inf:
  25. 		p7.append(i)
  26. 		i*=7
  27. 	i=1
  28. 	while i<=inf:
  29. 		p11.append(i)
  30. 		i*=11
  31.  
  32. def cnt(n, k):
  33. 	ans=0
  34. 	if k==2:
  35. 		for i in range(1, len(p2)):
  36. 			if p2[i]>n:
  37. 				return ans
  38. 			ans+=1
  39. 	if k==3:
  40. 		for i in range(len(p2)):
  41. 			if p2[i]>n:
  42. 				return ans
  43. 			for j in range(1, len(p3)):
  44. 				if p2[i]*p3[j]>n:
  45. 					break
  46. 				ans+=1
  47. 	if k==5:
  48. 		for i in range(len(p2)):
  49. 			if p2[i]>n:
  50. 				return ans
  51. 			for j in range(len(p3)):
  52. 				if p2[i]*p3[j]>n:
  53. 					break
  54. 				for l in range(1, len(p5)):
  55. 					if p2[i]*p3[j]*p5[l]>n:
  56. 						break
  57. 					ans+=1
  58. 	if k==7:
  59. 		for i in range(len(p2)):
  60. 			if p2[i]>n:
  61. 				return ans
  62. 			for j in range(len(p3)):
  63. 				if p2[i]*p3[j]>n:
  64. 					break
  65. 				for l in range(len(p5)):
  66. 					if p2[i]*p3[j]*p5[l]>n:
  67. 						break
  68. 					for m in range(1, len(p7)):
  69. 						if p2[i]*p3[j]*p5[l]*p7[m]>n:
  70. 							break
  71. 						ans+=1
  72. 	if k==11:
  73. 		for i in range(len(p2)):
  74. 			if p2[i]>n:
  75. 				return ans
  76. 			for j in range(len(p3)):
  77. 				if p2[i]*p3[j]>n:
  78. 					break
  79. 				for l in range(len(p5)):
  80. 					if p2[i]*p3[j]*p5[l]>n:
  81. 						break
  82. 					for m in range(len(p7)):
  83. 						if p2[i]*p3[j]*p5[l]*p7[m]>n:
  84. 							break
  85. 						for p in range(1,len(p11)):
  86. 							if p2[i]*p3[j]*p5[l]*p7[m]*p11[p]>n:
  87. 								break
  88. 							ans+=1
  89.  
  90. def bin(lo, n, k, z):
  91. 	hi=inf
  92. 	while lo<hi:
  93. 		mid=(lo+hi)/2
  94. 		r=cnt(mid, k)
  95. 		if r-z>=n:
  96. 			hi=mid
  97. 		else:
  98. 			lo=mid+1
  99. 	return lo
  100.  
  101. pre()
  102. t=int(raw_input())
  103. while t:
  104. 	t=t-1
  105. 	s=raw_input().split()
  106. 	a=int(s[0])
  107. 	k=int(s[1])
  108. 	n=int(s[2])
  109. 	z=cnt(a-1, k)
  110. 	res=bin(a, n, k, z)
  111. 	print res
Success #stdin #stdout 2.1s 9032KB
comments (?)
stdin
copy 
5
3 2 4
5 3 4
4 5 4
5 7 4
3 11 4
stdout
copy 
32
18
20
28
44
https://ideone.com/YukrSo
language:
Python (cpython 2.7.16)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!