結果
問題 |
No.2039 Copy and Avoid
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:51:06 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,554 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 90,752 KB |
最終ジャッジ日時 | 2025-06-12 20:55:59 |
合計ジャッジ時間 | 6,651 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 30 |
ソースコード
import sys import math def get_divisors(n): divisors = set() for i in range(1, int(math.isqrt(n)) + 1): if n % i == 0: divisors.add(i) divisors.add(n // i) return sorted(divisors) def factorize(n): factors = [] i = 2 while i * i <= n: while n % i == 0: factors.append(i) n //= i i += 1 if n > 1: factors.append(n) return factors def generate_factor_sequences(n, current, start, memo): if n == 1: return [[]] if (n, start) in memo: return memo[(n, start)] sequences = [] i = start while i * i <= n: if n % i == 0: if i >= start: for seq in generate_factor_sequences(n // i, current + [i], i, memo): sequences.append([i] + seq) i += 1 if n >= start: sequences.append([n]) memo[(n, start)] = sequences return sequences def main(): N, M, A, B = map(int, sys.stdin.readline().split()) forbidden = set(map(int, sys.stdin.readline().split())) forbidden_set = set(forbidden) divisors = get_divisors(N) min_cost = float('inf') for P in divisors: if P == 0: continue if P == 1: continue factors = factorize(P) memo = {} sequences = generate_factor_sequences(P, [], 2, memo) for seq in sequences: product = 1 valid = True for i in range(len(seq)): f = seq[i] prev_product = product for t in range(2, f + 1): x = prev_product * t if x in forbidden_set: valid = False break if not valid: break product *= f if not valid: continue K = N // P if K < 1: continue final_product = product for t in range(2, K + 1): x = final_product * t if x in forbidden_set: valid = False break if not valid: continue cost = 0 for f in seq: cost += (f - 1) * A + B cost += (K - 1) * A if cost < min_cost: min_cost = cost if min_cost != float('inf'): print(min_cost) else: print(-1) if __name__ == '__main__': main()