pythonを使い慣れていないとpythonでは解くのが厳しそうな問題。

問題

狐のCielは数直線上の原点にいる。彼は距離LiのジャンプをCiのコストを払うことによりできるようになる(点xにいるとすると、x+Li と x-Li に行くことができるようになる)。一度購入したジャンプは使い放題である。Cielはいくつかのジャンプを購入して、数直線上のすべての整数点にジャンプできるようになりたい。距離とコストのリストを与えられるので、Cielの望みを叶えるのにかかる最低コストを答える。無理なときは-1と出力する。制限はリストの個数 n ≦ 300, Li ≦ 10⁹ , Ci ≦ 10⁵。

解法

すべての点にジャンプできるようになるとは言い換えるといくつかのジャンプを組み合わせて距離1のジャンプをできるかどうかである。これは、購入したジャンプ距離の最大公約数が1であることと同じである。

これで問題はどういったジャンプを購入すれば費用を最小に抑えられるかになった。n が最大300なので、あるジャンプを使う使わないを考えていくのでは計算量が2³⁰⁰となり間に合わない。C++ならdpで解けるのだろうが、Li、Ciがともに大きいのでpythonだと若干不安が残る。そこで、dictを利用する。keyを最大公約数、valueをコストの合計として、ある最大公約数を実現するのに必要なもっとも小さなコストを更新していく。defaultdictを使えば、keyの存在判定をしなくてよくなるため記述が簡潔になり、処理もはやくなる。

from collections import defaultdict
from fractions import gcd
def inf(): return 10**9+7
    
N = int(raw_input())
L = map(int,raw_input().split())
C = map(int,raw_input().split())

S = defaultdict(inf)
S[0] = 0
for i in xrange(N):
    T = defaultdict(inf)
    for l in S:
        r = gcd(l,L[i])
        T[r] = min(T[r], S[l]+C[i])
    for r in T:
        S[r] = min(S[r], T[r])
print S[1] if 1 in S else -1