結果

問題 No.368 LCM of K-products
ユーザー ntuda
提出日時 2025-06-28 16:26:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 1,139 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 78,016 KB
最終ジャッジ日時 2025-06-28 16:26:08
合計ジャッジ時間 5,049 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10 ** 9 + 7

def PrimeList(N):
    P = [1] * (N + 1)
    P[0] = P[1] = 0
    for i in range(2, N + 1):
        if P[i]:
            for j in range(i + i, N + 1, i):
                P[j] = 0
    for i in range(N + 1):
        if P[i] == 1:
            PL.append(i)
    return PL

def adic(dic,x):
    if x in dic:
        dic[x] += 1
    else:
        dic[x] = 1
    return

def factorization(x):
    dic = {}
    for p in PL:
        if x in PLS:
            adic(dic,x)
            return dic
        while x % p == 0:
            adic(dic,p)
            x //= p
        if x == 1:
            return dic
    dic[x] = 1
    return dic

PL = []
PrimeList(int((10 ** 9)**0.5)+1)
PLS = set(PL)

N,K = map(int,input().split())
A = list(map(int,input().split()))
from collections import defaultdict
dic2 = defaultdict(list)
for i,a in enumerate(A):
    C = factorization(a)
    for k,v in C.items():
        dic2[k].append(v)

ans = 1
for k,vlist in dic2.items():
    if len(vlist) <= K:
        ans *= pow(k,sum(vlist),MOD)
    else:
        vlist.sort(reverse = True)
        ans *= pow(k,sum(vlist[:K]),MOD)
    ans %= MOD

print(ans)
0