[ARC085C] MUL
题意翻译
有 $N$ 个宝石,编号为 $1, 2, .., N$
你可以进行任意次以下操作(可以一次也不做)
- 选择一个正整数 $x$,将所有编号为 $x$ 的倍数的宝石打碎
最后,对于每个没有被打碎的宝石 $i$,你可以获得 $a_i$ 円。要注意的是,有些 $a_i$ 是负值,这意味着你要倒贴钱。
在最好的情况下,你能获得多少円呢?
## **数据范围**
所有输入的数都是整数
$1 \leq N \leq 100$
$ |a_i| \leq 10^9$
## **输入格式**
第一行一个整数 $N$,代表共有 $N$ 个宝石
第二行 $N$ 个整数,分别代表 $a_1, a_2, ..., a_N$
## **输出格式**
一行一个整数,表示你最多可以得到的钱
翻译提供者:魔塔哈奇
题目描述
[problemUrl]: https://arc085.contest.atcoder.jp/tasks/arc085_c
宝石が $ N $ 個あり,それぞれ $ 1,\ 2,\ ...,\ N $ と数が書かれています。
あなたは,以下の操作を好きなだけ行うことが出来ます(一度も行わなくてもよいです)。
- 正整数 $ x $ を選ぶ。 $ x $ の倍数が書かれた宝石を全て叩き割る。
そして, $ i $ が書かれていた宝石が割られずに残っていた場合, $ a_i $ 円貰います。 ただし,この $ a_i $ は負の場合もあり,その場合はお金を払わなくてはいけません。
うまく操作を行った時,あなたは最大で何円お金を貰えるでしょうか?
输入输出格式
输入格式
Input is given from Standard Input in the following format:
```
$ N $
$ a_1 $ $ a_2 $ $ ... $ $ a_N $
```
输出格式
Print the maximum amount of money that can be earned.
输入输出样例
输入样例 #1
6
1 2 -6 4 5 3
输出样例 #1
12
输入样例 #2
6
100 -100 -100 -100 100 -100
输出样例 #2
200
输入样例 #3
2
-1000 100000
输出样例 #3
99000
输入样例 #4
6
1 2 -6 4 5 3
输出样例 #4
12
输入样例 #5
6
100 -100 -100 -100 100 -100
输出样例 #5
200
输入样例 #6
2
-1000 100000
输出样例 #6
99000
说明
### 制約
- 入力は全て整数
- $ 1\ \leq\ N\ \leq\ 100 $
- $ |a_i|\ \leq\ 10^9 $
### Problem Statement
We have $ N $ gemstones labeled $ 1 $ through $ N $ .
You can perform the following operation any number of times (possibly zero).
- Select a positive integer $ x $ , and smash all the gems labeled with multiples of $ x $ .
Then, for each $ i $ , if the gem labeled $ i $ remains without getting smashed, you will receive $ a_i $ yen (the currency of Japan). However, $ a_i $ may be negative, in which case you will be charged money.
By optimally performing the operation, how much yen can you earn?
### Constraints
- All input values are integers.
- $ 1\ \leq\ N\ \leq\ 100 $
- $ |a_i|\ \leq\ 10^9 $
### Sample Explanation 1
宝石 $ 3,\ 6 $ を叩き割るのが最適です。
### Sample Explanation 3
全ての宝石を叩き割るのが最適です。
### Sample Explanation 5
It is optimal to smash Gem $ 3 $ and $ 6 $ .
### Sample Explanation 7
It is optimal to smash all the gems.