#include "bits/stdc++.h" // マクロ群 #define REP(i,n) for(int i=0;i PrimeFLG; void MakePrimeFLG(int period) { // 初期化 PrimeFLG = vector(period + 1, true); PrimeFLG[0] = false; PrimeFLG[1] = false; //// エラトステネスの篩を使って素数ではない物を更新する for (int i = 2; i * i < period; i++) // √priode まで繰り返す if (PrimeFLG[i] == true) // 素数の時だけ for (int j = i * i; j < period; j += i) // i を軸に倍々ループ PrimeFLG[j] = false; // i からなるすべての倍数は素数ではない } void Slove() { int M, N; SF("%d", &M); // 初期所持金 SF("%d", &N); // カップ麺の種類 vector C(N); REP(n, N) SF("%d", &C[n]); // 種類ごとの価格 sort(C.begin(), C.end()); // 小さい順に並べ替え // 素数のフラグリストを作る MakePrimeFLG(M); // 金額分の要素を持ったリストを作成する vector dp = vector(M, -1); // -1で初期化 // 残額をキーとして、その残額になったときに、 // 何個のカップ麺を買えたかをリストに記憶する dp[M] = 0; for (int money = M; money != -1; --money) { if (dp[money] == -1) continue; for (int kind = 0; kind < N; ++kind) { if (money - C[kind] > -1) { dp[money - C[kind]] = dp[money - C[kind]] > dp[money] + 1 ? dp[money - C[kind]] : dp[money] + 1; } else break; } } int ans = 0; // 一番多く買えた個数を結果に対して加算 ans += *max_element(dp.begin(), dp.end()); // 素数の残額キーに記憶された購入個数分はノーリスクで // 手に入ったこととなるため、その分を結果に対して加算 REP(m, M) if (dp[m] > -1 && PrimeFLG[m] == true) ans += dp[m]; PF("%d\n", ans); } int main() { Slove(); }