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