romesful

Untitled

Sep 28th, 2020
673
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. prime_divs_count = 0
  2. divisors = []
  3. prime_divs = []
  4.  
  5. def get_all_divisors(current_num, current_index):
  6.     global prime_divs_count, divisors, prime_divs
  7.     if (current_index >= prime_divs_count): return;
  8.  
  9.     get_all_divisors(current_num, current_index+1)
  10.     for i in range(1, 60):
  11.         current_num *= prime_divs[current_index]
  12.         if (current_num > m): return;
  13.  
  14.         divisors.append(current_num)
  15.         get_all_divisors(current_num, current_index+1)
  16.  
  17. def lower_bound(numbers, value):
  18.     left = -1
  19.     right = len(numbers) - 1
  20.  
  21.     while (right - left > 1):
  22.         middle = (left+right)//2
  23.  
  24.         if (numbers[middle] < value):
  25.             left = middle
  26.         else:
  27.             right = middle
  28.            
  29.     return right
  30.  
  31. b, m, n = input().split(' ')
  32. b = int(b)
  33. m = int(m)
  34. n = int(n)
  35.  
  36. b_for_fact = b
  37. i = 2
  38. while (i*i <= b_for_fact):
  39.     if (b_for_fact % i == 0):
  40.         prime_divs.append(i)
  41.         while (b_for_fact % i == 0):
  42.             b_for_fact //= i
  43.     i += 1
  44.  
  45. if (b_for_fact > 1): prime_divs.append(b_for_fact)
  46.  
  47. prime_divs_count = len(prime_divs)
  48.  
  49. get_all_divisors(1, 0)
  50.  
  51. divisors.sort()
  52.  
  53. #print(divisors)
  54.  
  55. current_query_index = 0
  56. while (current_query_index < n):
  57.     current_query_index += 1
  58.     a = int(input())
  59.     index_in_divisors = lower_bound(divisors, a)
  60.     appropriate_divisor = divisors[index_in_divisors]
  61.     if (appropriate_divisor >= a):
  62.         print(appropriate_divisor - a)
  63.     else:
  64.         print(-1)
  65.  
RAW Paste Data