No.719 Coprime
タグ : / 解いたユーザー数 37
作問者 :
startcpp
/ テスター :
butsurizuki
問題文
うさぎは、$2$～$N$の数字が書かれたカードを$1$枚ずつ、合計$N - 1$枚用意しました。
うなぎは、その中からカードを好きなだけ選びます。
うなぎがカードを選び終えると、うさぎは、うなぎが選んだカードの組み合わせに応じてお金を渡します。
具体的には、
うなぎが選んだカードに書かれた値の集合を$U$としたとき、$U$のどの異なる$2$つの値も互いに素であれば、
うさぎは「うなぎが選んだカードに書かれた値の合計」[円]のお金を（うなぎに）渡します。
うなぎがもらえる金額を$X$[円]としたとき、$X$の最大値を求めてください。
入力
N
$2 \le N \le 1262$
出力
$X$の最大値を$1$行で出力してください。 最後に改行してください。
サンプル
サンプル1
入力
6
出力
12
うさぎは$2$,$3$,$4$,$5$,$6$の書かれたカードを$1$枚ずつ用意しています。
うなぎは、「$3$が書かれたカード, $4$が書かれたカード, $5$が書かれたカード」を選ぶことで、もらえる金額を最大化できます。
このとき得られる金額は、$3 + 4 + 5 = 12$円です。
しかし、「$4$が書かれたカード, $5$が書かれたカード, $6$が書かれたカード」を全て選んだ場合、お金はもらえません。
これは、$4$と$6$が互いに素ではない(最大公約数が$1$にならない)からです。
サンプル2
入力
2
出力
2
カードを$1$枚だけ選んでもお金をもらうことができます。
サンプル3
入力
18
出力
79
例えば、${7, 11, 13, 15, 16, 17}$の書かれたカード（$6$枚）を選ぶことで、$79$円のお金をもらうことができます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。