bitDPを想定しています.

追記: hirono999さんからdp[i番目まで][j個とったとき][gcdの値]で解けると教えていただきました. ありがとうございます. 全然気づきませんでした. これだとAi500A_i \leq 500でも解けそうです.