Submission #62797452

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def divisors(x):
    small, large = [], []
    i = 1
    while i * i <= x:
        if x % i == 0:
            small.append(i)
            if i * i != x:
                large.append(x // i)
        i += 1
    return large + small[::-1]
import sys
from collections import defaultdict
input_data = sys.stdin.read().split()
it = 0
n = int(input_data[it]); it += 1
k = int(input_data[it]); it += 1
a = list(map(int, input_data[it:it+n]))
mx = max(a)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def divisors(x):
    small, large = [], []
    i = 1
    while i * i <= x:
        if x % i == 0:
            small.append(i)
            if i * i != x:
                large.append(x // i)
        i += 1
    return large + small[::-1]

import sys
from collections import defaultdict

input_data = sys.stdin.read().split()
it = 0
n = int(input_data[it]); it += 1
k = int(input_data[it]); it += 1
a = list(map(int, input_data[it:it+n]))

mx = max(a)
tmp = [0] * (mx + 1)
for x in a:
    tmp[x] += 1

mt = [0] * (mx + 1)
for d in range(mx, 0, -1):
    s = 0
    for i in range(d, mx + 1, d):
        s += tmp[i]
    mt[d] = s

cache = {}       
divs_cache = {}  

for ai in a:
    if ai in cache:
        print(cache[ai])
        continue 
    if ai not in divs_cache:
        divs_cache[ai] = divisors(ai)
    for d in divs_cache[ai]:
        if mt[d] >= k:
            cache[ai] = d
            print(d)
            break

Submission Info

Judge Result