結果

問題 No.2039 Copy and Avoid
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:53:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,193 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 81,992 KB
実行使用メモリ 93,140 KB
最終ジャッジ日時 2025-06-12 20:57:24
合計ジャッジ時間 6,611 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

def get_divisors(factors):
    divisors = [1]
    for p in factors:
        exponents = [p**e for e in range(1, factors[p] + 1)]
        new_divisors = []
        for d in divisors:
            for e in exponents:
                new_divisors.append(d * e)
        divisors += new_divisors
    divisors = list(set(divisors))
    divisors.sort()
    return divisors

def main():
    import sys
    from collections import defaultdict
    import heapq

    N, M, A, B = map(int, sys.stdin.readline().split())
    C = list(map(int, sys.stdin.readline().split()))
    forbidden = set(C)

    if 1 in forbidden or N in forbidden:
        print(-1)
        return

    factors = factorize(N)
    divisors = get_divisors(factors)
    D = divisors

    adj = defaultdict(list)

    for d in D:
        if d == N:
            continue
        for m in D:
            if m > d and m % d == 0:
                f = m // d
                if f < 2:
                    continue
                valid = True
                for c in forbidden:
                    if c % d == 0:
                        q = c // d
                        if 1 <= q <= f:
                            valid = False
                            break
                if valid:
                    cost = (f - 1) * A
                    if m != N:
                        cost += B
                    adj[d].append((m, cost))

    INF = float('inf')
    dist = {d: INF for d in D}
    dist[1] = 0
    heap = []
    heapq.heappush(heap, (0, 1))
    visited = set()

    while heap:
        current_dist, u = heapq.heappop(heap)
        if u in visited:
            continue
        if u == N:
            print(current_dist)
            return
        visited.add(u)
        for v, cost in adj[u]:
            if dist[v] > current_dist + cost:
                dist[v] = current_dist + cost
                heapq.heappush(heap, (dist[v], v))

    print(-1)

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