結果

問題 No.2039 Copy and Avoid
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:57:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,532 bytes
コンパイル時間 355 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 89,216 KB
最終ジャッジ日時 2025-03-26 15:57:37
合計ジャッジ時間 6,694 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def factorize(n):
    factors = {}
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n = n // 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n = n // i
        i += 2
    if n > 1:
        factors[n] = 1
    return factors

def generate_divisors(factors):
    divisors = [1]
    for p, exp in factors.items():
        current_length = len(divisors)
        p_pows = []
        for e in range(1, exp + 1):
            p_pows.append(p ** e)
        for pow_p in p_pows:
            for i in range(current_length):
                divisors.append(divisors[i] * pow_p)
    return sorted(divisors)

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    A = int(input[idx]); idx +=1
    B = int(input[idx]); idx +=1
    C = list(map(int, input[idx:idx+M]))
    forbidden_set = set(C)
    if N == 1:
        print(-1)
        return
    
    factors = factorize(N)
    divisors = generate_divisors(factors)
    if N not in divisors:
        divisors.append(N)
    divisors = sorted(divisors)
    
    dp = {d: float('inf') for d in divisors}
    dp[1] = 0
    
    for d in divisors:
        if d == 1:
            continue
        possible_prevs = [prev for prev in divisors if prev < d and d % prev == 0]
        for prev in possible_prevs:
            s = d // prev
            if s < 2:
                continue
            invalid = False
            for c in C:
                if c % prev != 0:
                    continue
                q = c // prev
                if 2 <= q <= s:
                    invalid = True
                    break
            if not invalid:
                if dp[prev] + (s-1)*A + B < dp[d]:
                    dp[d] = dp[prev] + (s-1)*A + B
    
    min_cost = float('inf')
    for d in divisors:
        if d >= N:
            continue
        if N % d != 0:
            continue
        k = (N // d) - 1
        if k < 0:
            continue
        invalid = False
        for c in C:
            if c < d * 2:
                continue
            if c > d * k:
                continue
            if c % d == 0:
                invalid = True
                break
        if not invalid:
            total_cost = dp[d] + k * A
            if total_cost < min_cost:
                min_cost = total_cost
    
    print(-1 if min_cost == float('inf') else min_cost)

if __name__ == '__main__':
    main()
0