# 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