No.937 Ultra Sword
Added 11/30 17:55) after_contest has been added to the test cases.
Problem Statement
The hero $null$ has obtained the Ultra Sword.
There are $N$ monsters in the dungeon, and the $HP$ of the $i$-th monster is $A_i$.
By swinging the Ultra Sword, $null$ can sacrifice $1$ monster, the $i$-th one, and for all monsters having $HP$ that is a positive integer multiple of that monster's $HP$,
reduce their $HP$ down to the value obtained by dividing it by $A_i$.
When this happens, the $HP$ of the sacrificed monster becomes $1$ and the Ultra Sword breaks, so the Ultra Sword cannot be swung $2$ or more times.
In addition, $null$ is also an excellent magician and can use the following $3$ types of magic any number of times.
Here, $null$ wants to make the sum of the $HP$ of all monsters as small as possible. Find the minimum possible sum of the $HP$ of all monsters when acting optimally.
Here, $xor$ denotes the exclusive OR taken per $bit$.
Input
$N$ $A_1,A_2,....A_N$
$2\le N \le 10^5$
$1\le A_i\le 10^5$
All inputs are integers.
Output
Print a newline at the end.
Sample
Sample 1
Input
3 10 20 30
Output
6
If you swing the Ultra Sword sacrificing the $1$st monster, the $HP$ of the $2$nd monster becomes $2$, and
the $HP$ of the $3$rd monster becomes $3$, so the sum of the $HP$ of all monsters becomes $6$, which is the minimum.
Sample 2
Input
4 28 24 32 20
Output
26
Create a monster whose $HP$ is the $xor$ of the $HP$ of the $1$st monster and the $2$nd monster. (Call this the $5$th monster.)
The $HP$ of the $5$th monster is $4$, and swinging the Ultra Sword with the $5$th monster as the sacrifice makes the sum of the $HP$ of all monsters $27$.
Then, using the $3$rd magic makes the $HP$ of the $5$th monster $0$, and the sum of the $HP$ of all monsters becomes $26$, which is the minimum.
Sample 3
Input
5 232 232 232 232 232
Output
5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
leafirby
otamay6