Problem:

Electric Metronome

  A boy PCK is playing with N electric metronomes. The i-th metronome is set to tick every t_i seconds. He started all of them simultaneously.

He noticed that, even though each metronome has its own ticking interval, all of them tick simultaneously from time to time in certain intervals. To explore this interesting phenomenon more fully, he is now trying to shorten the interval of ticking in unison by adjusting some of the metronomes’ interval settings. Note, however, that the metronomes do not allow any shortening of the intervals.
  

  Given the number of metronomes and their preset intervals t_i (sec), write a program to make the tick-in-unison interval shortest by adding a non-negative integer d_i to the current interval setting of the i-th metronome, and report the minimum value of the sum of all d_i.

Input

  The input is given in the following format.

N
t_1
t_2
:
t_N

The first line provides the number of metronomes N (1 ≤ N ≤ 105). Each of the subsequent N lines provides the preset ticking interval t_i (1 ≤ t_i ≤ 104) of the i-th metronome.
  

Output

  Output the minimum value.

Sample Input 1

3
3
6
8

Sample Output 1

3

If we have three metronomes each with a ticking interval of 3, 6, and 8 seconds, respectively, simultaneous activation of these will produce a tick in unison every 24 seconds. By extending the interval by 1 second for the first, and 2 seconds for the second metronome, the interval of ticking in unison will be reduced to 8 seconds, which is the shortest possible for the system.
  

Sample Input 2

2
10
10

Sample Output 2

0

If two metronomes are both set to 10 seconds, then simultaneous activation will produce a tick in unison every 10 seconds, which is the shortest possible for this system.
  



Sample input:
3
3
6
8


Sample output:
3

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
n = int(input())
tlst = sorted([int(input()) for _ in range(n)])
max_t = tlst[-1]
divisors = [i for i in range(1, max_t + 1) if max_t % i == 0]

ans = 0
for t in tlst:
  ind = bl(divisors, t)
  ans += divisors[ind] - t
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = [int(input()) for i in range(N)]
T.sort()
if N == 1:
    ans = 0
else:
    y = T[-1]
    R = []
    for x in range(1, y+1):
        if y % x == 0:
            R.append(x)
    cur = ans = 0
    for t in T:
        while R[cur] < t:
            cur += 1
        ans += R[cur] - t
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
t = [int(input()) for i in range(N)]
M = max(t)
div = [i for i in range(1, M + 1) if M % i == 0]
di = 0
for i in t:
    for j in div:
        if i <= j:
            di += j - i
            break
print(di)

Submission status: Accepted

Solution code:
N = int(input())
lst = [int(input()) for _ in range(N)]
max_ = max(lst)
divisors = []
d = 0

for i in range(1, int(max_**0.5) + 1):
    if max_ % i == 0:
        divisors.append(i)
        divisors.append(max_ // i)
divisors.sort()

for i in sorted(lst):
    for divisor in divisors:
        if i <= divisor:
            d += divisor - i
            break

print(d)

Submission status: Accepted

Solution code:
n = int(input())
max_t = 0
timing = []
for i in range(n):
    timing.append(int(input()))
    if timing[i] > max_t : max_t = timing[i]

divisor = []
for i in range(1,(max_t>>1)+1):
    if max_t%i == 0 : divisor.append(i)
divisor.append(max_t)
    
adj = 0
for t in timing :
    for d in divisor :
        if  d >= t :
            adj += d - t
            break
print(adj)

Submission status: Accepted

Solution code:
import math
n = int(input())
lis = []
cou = 0
ans = 0
for i in range(n):
  a = int(input())
  cou = max(cou,a)
  lis.append(a)
num = []
for i in range(1,cou+1):
  if cou % i == 0:
    num.append(i)
for nu in lis:
  co = 0
  while num[co] < nu:
    co += 1
  ans += (num[co]-nu)
print(ans)

Submission status: Accepted

Solution code:
def divisor_list(x):
    return tuple([i for i in range(1, x+1) if x % i == 0])

N = int(input())
t = [int(input()) for _ in range(N)]
div = divisor_list(max(t))
di = 0
for i in range(N):
    j = 0
    while div[j] < t[i]:
        j += 1
    else:
        di += div[j] - t[i]
print(di)