No.719 Coprime
タグ : / 解いたユーザー数 41
作問者 :
startcpp
/ テスター :
butsurizuki
Problem Statement
Usagi prepared $1$ card for each number from $2$ to $N$, for a total of $N - 1$ cards.
Unagi chooses as many of these cards as desired.
Once Unagi has finished choosing cards, Usagi gives money according to the combination of cards Unagi chose.
Specifically,
let $U$ be the set of values written on the cards Unagi chose. If every $2$ distinct values in $U$ are coprime,
Usagi gives (Unagi) an amount of money equal to "the sum of the values written on the cards Unagi chose" [yen].
Let $X$ [yen] be the amount of money Unagi can receive. Find the maximum value of $X$.
Input
N
$2 \le N \le 1262$
Output
Print the maximum value of $X$ on $1$ line. Print a newline at the end.
Sample
Sample 1
Input
6
Output
12
Usagi has prepared cards with $2$,$3$,$4$,$5$,$6$ written on them, $1$ card each.
Unagi can maximize the amount received by choosing "the card with $3$ written on it, the card with $4$ written on it, and the card with $5$ written on it".
The amount obtained in this case is $3 + 4 + 5 = 12$ yen.
However, if Unagi chooses all of "the card with $4$ written on it, the card with $5$ written on it, and the card with $6$ written on it", no money is received.
This is because $4$ and $6$ are not coprime (their greatest common divisor is not $1$).
Sample 2
Input
2
Output
2
Unagi can receive money even when choosing only $1$ card.
Sample 3
Input
18
Output
79
For example, by choosing the cards ($6$ cards) with ${7, 11, 13, 15, 16, 17}$ written on them, Unagi can receive $79$ yen.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。