問題一覧 > 通常問題

No.3502 GCD Knapsack

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 58
作問者 : Naru820 / テスター : Nzt3 irinoirino Solalyth
ProblemId : 13218 / CPCTF 2026: PPC (順位表) / 自分の提出
問題文最終更新日: 2026-04-11 20:01:28
CPCTF 2026: PPCの他の問題:

問題文

$N$ 個の品物があります。$i$ 個目の品物の重みは $X_i$ で、価値は $Y_i$ です。

選んだ品物の重みの最大公約数が $W$ 以上になるように品物を $1$ 個以上選ぶことができるかどうか判定し、できるならば選んだ品物の価値の和として考えられる最大値を求めてください。

制約

  • $1 \leq N,W \leq 2 \times 10^5$
  • $1 \le X_i \le 2\times 10^5$
  • $1 \le Y_i \le 10^9$
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

$N \ W$
$X_1 \ X_2 \ldots X_N$ 
$Y_1 \ Y_2 \ldots Y_N$

出力

品物を選ぶことが出来ない場合は $0$ を出力してください。できる場合は、品物の価値の和として考えられる最大値を出力してください。

サンプル

サンプル1
入力
3 2
4 2 3
5 2 8
出力
8

品物の選び方であって、重みの最大公約数が $2$ 以上になるのは以下のような選び方です。

  • 品物 $1$ を選ぶ。価値の合計は $5$ である。
  • 品物 $2$ を選ぶ。価値の合計は $2$ である。
  • 品物 $3$ を選ぶ。価値の合計は $8$ である。
  • 品物 $1,2$ を選ぶ。価値の合計は $7$ である。

よって、価値の合計の最大値は $8$ なので、答えは $8$ です。

サンプル2
入力
5 10
4 6 2 3 9
5 8 2 4 6
出力
0

重みの最大公約数が $10$ 以上になるように品物を選ぶことができません。よって $0$ を出力してください。

サンプル3
入力
20 26
6736 1887 1758 918 1150 1210 1975 958 763 1784 224 25 1794 15 963 1314 615 1526 7301 680
752 18717 225699 70 6427 314 61610 587 343 10924 1250 290 64100 5315 8566 84972 4135 2946 11 40640
出力
225699

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。