Submission #62795180

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):
        divs = []
        i = 1
        while i*i <= x:
            if x % i == 0:
                divs.append(i)
                if i*i != x:
                    divs.append(x//i)
            i += 1
        return divs
n,k=map(int,input().split())
a=list(map(int,input().split()))
from collections import defaultdict
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):
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

n,k=map(int,input().split())
a=list(map(int,input().split()))

from collections import defaultdict
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=defaultdict(int)
for ai in a:
    if ai in cache:
        print(cache[ai])
    div=divisors(ai)
    div.sort(reverse=True)
    flg=1
    for d in div:
        if mt[d]>=k:
            cache[ai]=d
            flg=0
            print(cache[ai])
            break
    if flg:
        cache[ai]=1
        print(1)

Submission Info

Judge Result