結果

問題 No.3717 GCD LCM GCD
コンテスト
ユーザー seroze
提出日時 2026-09-24 02:56:45
言語 Python3
(3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 310 ms / 2,000 ms
+ 851µs
コード長 2,642 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 54 ms
コンパイル使用メモリ 15,232 KB
実行使用メモリ 59,356 KB
最終ジャッジ日時 2026-09-24 02:56:51
合計ジャッジ時間 3,608 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

MOD = 998244353


def solve():
    input = sys.stdin.readline

    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    M = max(A)

    # ------------------------------------------------------------
    # Smallest Prime Factor sieve
    # ------------------------------------------------------------
    spf = list(range(M + 1))

    if M >= 1:
        spf[1] = 1

    i = 2
    while i * i <= M:
        if spf[i] == i:
            for j in range(i * i, M + 1, i):
                if spf[j] == j:
                    spf[j] = i
        i += 1

    # ------------------------------------------------------------
    # cnt[p][e] = number of A_i whose p-adic exponent is exactly e
    #
    # Example:
    # A_i = 12 = 2^2 * 3
    # => cnt[2][2] += 1
    # => cnt[3][1] += 1
    #
    # e <= 19 because 2^20 > 10^6.
    # ------------------------------------------------------------
    MAX_E = 19
    cnt = {}

    for x in A:
        while x > 1:
            p = spf[x]
            e = 0

            while x % p == 0:
                x //= p
                e += 1

            arr = cnt.get(p)
            if arr is None:
                arr = [0] * (MAX_E + 1)
                cnt[p] = arr

            arr[e] += 1

    # ------------------------------------------------------------
    # For each prime p:
    #
    # Find the largest e such that p^e occurs in B(P)
    # for EVERY permutation P.
    #
    # Let:
    #   good = number of elements divisible by p^e
    #   bad  = N - good
    #
    # We can avoid K consecutive good elements iff
    #
    #   good <= (bad + 1) * (K - 1)
    #
    # Therefore p^e is unavoidable iff
    #
    #   good > (bad + 1) * (K - 1)
    # ------------------------------------------------------------

    answer = 1

    for p, freq in cnt.items():

        # suffix[e] = number of elements with v_p(A_i) >= e
        suffix = [0] * (MAX_E + 2)

        running = 0
        for e in range(MAX_E, 0, -1):
            running += freq[e]
            suffix[e] = running

        best_e = 0

        for e in range(1, MAX_E + 1):
            good = suffix[e]

            if good == 0:
                break

            bad = N - good

            # K consecutive good elements are unavoidable.
            if good > (bad + 1) * (K - 1):
                best_e = e
            else:
                # As e increases, good only decreases,
                # so once the condition fails it will keep failing.
                break

        if best_e:
            answer = answer * pow(p, best_e, MOD) % MOD

    print(answer)


if __name__ == "__main__":
    solve()
0