Challenge: Bear And Cryptography
Subdomeniu: Number Theory (number-theory)
Scor cont: 100.0 / 100
Submission status: Accepted
Submission score: 1.0
Submission ID: 464776295
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/bear-and-cryptography/problem
Cerinta
Limak is a little bear who loves school. Today was his first lesson in cryptography, and the teacher assigned some difficult homework—to find any number with exactly $K$ divisors. Limak wants to go the extra mile and find the biggest possible number; however, his teacher explained that there are arbitrarily large numbers with this property.
To give this little bear a more achievable challenge, the teacher advised him to consider only numbers not greater than $N$.
Given $N$ and $K$, what is the largest number Limak can find?Input Format
The first line contains an integer, $T$ (the number of test cases).
The $T$ subsequent lines of test cases each contain two space-separated integers, $N$ and $K$, respectively.Output Format
For each test case, print the biggest number Limak can find on a new line. Print $-1$ if no such number exists.Constraints
* $1 \le T \le 50$
* $1 \le N \le 10^{12}$
* $1 \le K \le 40$Cod sursa
#!/bin/python3
import math
import random
def gcd(a, b):
while b > 0:
c = a % b
a = b
b = c
return a
def is_prime(k):
small = [2,3,5,7,11]
if k in small:
return True
if k % 2 == 0:
return False
odd = k - 1
e = 0
while odd % 2 == 0:
e += 1
odd = odd//2
for p in small:
num = pow(p, odd, k)
check = False
if num == 1 or num == k - 1:
continue
for i in range(e):
num = pow(num, 2, k)
if num == k - 1:
check = True
break
if num == 1:
return False
if not check and num != 1:
return False
return True
factorizations = [[],
[],
[[2]],
[[3]],
[[4], [2, 2]],
[[5]],
[[6], [3, 2]],
[[7]],
[[8], [4, 2], [2, 2, 2]],
[[9], [3, 3]],
[[10], [5, 2]],
[[11]],
[[12], [6, 2], [3, 2, 2], [4, 3]],
[[13]],
[[14], [7, 2]],
[[15], [5, 3]],
[[16], [8, 2], [4, 2, 2], [2, 2, 2, 2], [4, 4]],
[[17]],
[[18], [9, 2], [3, 3, 2], [6, 3]],
[[19]],
[[20], [10, 2], [5, 2, 2], [5, 4]],
[[21], [7, 3]],
[[22], [11, 2]],
[[23]],
[[24], [12, 2], [6, 2, 2], [3, 2, 2, 2], [4, 3, 2], [8, 3], [6, 4]],
[[25], [5, 5]],
[[26], [13, 2]],
[[27], [9, 3], [3, 3, 3]],
[[28], [14, 2], [7, 2, 2], [7, 4]],
[[29]],
[[30], [15, 2], [5, 3, 2], [10, 3], [6, 5]],
[[31]],
[[32], [16, 2], [8, 2, 2], [4, 2, 2, 2], [2, 2, 2, 2, 2], [4, 4, 2], [8, 4]],
[[33], [11, 3]],
[[34], [17, 2]],
[[35], [7, 5]],
[[36],
[18, 2],
[9, 2, 2],
[3, 3, 2, 2],
[6, 3, 2],
[12, 3],
[4, 3, 3],
[9, 4],
[6, 6]],
[[37]],
[[38], [19, 2]],
[[39], [13, 3]],
[[40], [20, 2], [10, 2, 2], [5, 2, 2, 2], [5, 4, 2], [10, 4], [8, 5]]]
'''
factorizations = [[],[],[[2]]]
def same_arr(a, b):
a = [i for i in a]
b = [j for j in b]
if len(a) != len(b):
return False
for thing in a:
if thing not in b:
return False
b.remove(thing)
return True
for i in range(3, 41):
facts = [[i]]
if is_prime(i):
factorizations.append(facts)
continue
for j in range(2, int(i**.5) + 1):
if i % j == 0:
fact = [j]
for other_fact in factorizations[i//j]:
new_fact = fact + other_fact
app = True
for thing in facts:
if same_arr(thing, new_fact):
app = False
break
if app:
facts.append(fact + other_fact)
factorizations.append(facts)
'''
def sieve(bound):
arr = [1 for i in range(bound - 2)]
arr.insert(0, 0)
arr.insert(0, 0)
ps = []
l = len(arr)
sq = 0
for i, val in enumerate(arr):
if sq > bound:
break
elif val == 1:
ind = i
ps.append(i)
for ind in range(sq, l, i):
arr[ind] = 0
sq = sq + 2* i + 1
for j in range(i, l):
if arr[j] == 1:
ps.append(j)
return ps
primes = sieve(1000)
bigPrimes = sieve(pow(10, 6))
smallPrimes = sieve(30)
midPrimes = sieve(1000)
def num_divs(d):
prod = 1
for k, v in d.items():
prod = prod * (v + 1)
return prod
def pollard_rho(n):
while True:
c = random.randint(2, n-1)
f = lambda x: x**2 + c
x = y = 2
d = 1
while d == 1:
x = f(x) % n
y = f(f(y)) % n
d = gcd((x - y) % n, n)
if d != n: return d
def smart_factor(n):
d = dict()
for div in primes:
while n % div == 0:
if div in d:
d[div] += 1
else:
d[div] = 1
n = n // div
if n == 1:
break
if n == 1:
return d
if not is_prime(n):
div = pollard_rho(n) #parameters should be chosen so that n has at most 4 prime factors
divs = []
n = n // div
if not is_prime(n):
div2 = pollard_rho(n)
div3 = n // div2
if not is_prime(div2):
div4 = pollard_rho(div2)
div5 = div2 // div4
divs.append(div4)
divs.append(div5)
else:
divs.append(div2)
if not is_prime(div3):
div4 = pollard_rho(div3)
div5 = div3 // div4
divs.append(div4)
divs.append(div5)
else:
divs.append(div3)
else:
divs.append(n)
if not is_prime(div):
div2 = pollard_rho(div)
div3 = div // div2
if not is_prime(div2):
div4 = pollard_rho(div2)
div5 = div2 // div4
divs.append(div4)
divs.append(div5)
else:
divs.append(div2)
if not is_prime(div3):
div4 = pollard_rho(div3)
div5 = div3 // div4
divs.append(div4)
divs.append(div5)
else:
divs.append(div3)
else:
divs.append(div)
for div in divs:
if div in d:
d[div] += 1
else:
d[div] = 1
else:
d[n] = 1
return d
def condition(sq, n):
if sq**2 <= n and (sq + 1)**2 > n:
return True
return False
def int_sqrt(n):
guess = n // 2
while not condition(guess, n):
guess = (guess + n//guess) // 2
return guess
def all_twos(a):
for thing in a:
if thing > 4:
return False
return True
def all_threes(a):
for thing in a:
if thing != 3:
return False
return True
#Implement 9, 27, and 30 better.
#if it's 9, we only check primes up to the 4th root of n. Symmetry tells us this should work.
#if it's 27, the smallest number has to be less than 100-ish by symmetry. Check the primes up
#to 100-ish for the smallest prime, and then it reduces to 9. Don't forget to check the other
#factorizations of 27, but those are really fast.
#if it's 30, the 4th power must correspond to a number less than 13-ish, the 2nd power must be
#less than 200-ish, and that should not be a hard check. Again don't forget to check the other
#factorizations of 30.
def solve_9(n, i):
biggest = -1
if n < 2:
return -1
for j in range(i, len(midPrimes)):
p = midPrimes[j]
res = n//pow(p, 2)
if res <= 3:
break
num = int_sqrt(res)
while num > p and not is_prime(num):
num = num - 1
if num <= p:
break
ans = pow(p, 2) * pow(num, 2)
if ans > biggest:
biggest = ans
return biggest
def solve_27(n):
biggest = -1
for i in range(len(midPrimes)):
p = midPrimes[i]
ans = solve_9(n//pow(p,2), i+1)
if ans*pow(p, 2) > biggest:
biggest = ans*pow(p,2)
return biggest
def solve_30(n):
biggest = -1
n2 = n
for p in smallPrimes:
for q in midPrimes:
if p != q:
n = n2
n = n // pow(p, 4)
n = n // pow(q, 2)
while n > 1 and not is_prime(n):
n = n - 1
ans = n * pow(p, 4) * pow(q, 2)
if ans > biggest:
biggest = ans
return biggest
def solve(n, fact):
if n < 2:
return -1
if len(fact) == 1:
root = fact[0] - 1
n2 = int(n**(1/root))
while n2**root < n:
n2 += 1
while n2**root > n and n2 > 1:
n2 = n2 - 1
if n2 <= 1:
return -1
while n2 > 1 and not is_prime(n2):
n2 = n2 - 1
if n2 == 1:
return -1
return pow(n2, root)
ans = 0
i = 0
biggest = -1
while ans != -1:
base = pow(bigPrimes[i], fact[0] - 1)
start = n // base
root = fact[1] - 1
n2 = int(start**(1/root))
while n2**root < start:
n2 += 1
while n2**root > start and n2 > 1:
n2 = n2 - 1
if n2 <= 1:
break
while (n2 > 1 and not is_prime(n2)) or n2 == bigPrimes[i]:
n2 = n2 - 1
if n2 == 1:
break
ans = n2**root
if ans*base > biggest:
biggest = ans*base
i += 1
return biggest
if __name__ == '__main__':
T = int(input())
#begin = time.time()
for thing in range(T):
NK = input().split()
N = int(NK[0])
K = int(NK[1])
if K == 1:
print(1)
continue
if K == 2:
if N == 1:
print(-1)
continue
while not is_prime(N):
N = N - 1
print(N)
continue
if is_prime(K):
root = K - 1
N2 = int(N**(1/root))
while N2**root < N:
N2 += 1
if N2**root > N:
N2 = N2 - 1
if N2 <= 1:
print(-1)
continue
while not is_prime(N2):
N2 = N2 - 1
print(pow(N2, root))
continue
biggest = -1
if (len(factorizations[K]) == 2 and (K != 4 and K != 6)) or (K in [27, 30]):
for thing in factorizations[K]:
if thing == [3, 3]:
ans = solve_9(N, 0)
elif thing == [3,3,3]:
ans = solve_27(N)
elif thing == [5,3,2]:
ans = solve_30(N)
else:
ans = solve(N, thing)
if ans > biggest:
biggest = ans
print(biggest)
else:
d = smart_factor(N)
while num_divs(d) != K:
N = N - 1
d = smart_factor(N)
print(N)
HackerRank Number Theory – Bear And Cryptography