Hi to everyone! I decided to create a blog with some problem which was invented by me several years ago and only simple version of it was used in municipal stage of all-russian school olympiad in Kaliningrad. I wanted to use it somewhere but now I understand that it is not possible anymore because very very similar problem with similar ideas was used in codeforceas round 858(it was f1-f2). I should have used it earlier somewhere and it is my second time that I lost my problem(first was div2 C from some old round). Now I just post it here so feel free to solve it and post your solutions. Later I can write my solution.↵
Warning: if you haven't participated in round 858 and want to do it virtually or just solve problems from there then I advice you not to read it because you may get spoilers.↵
↵
<spoiler summary="Problem">↵
...You are given an array of up to 500000 numbers which can be up to 10^30. Define the cost of the subset of the array as sum of elements of this subset plus gcd of elements of this subset. For every k from 1 to n print the maximum possible cost of some subset of size k. TL:8 sec. (By the way on the municipal stage there was only k=2).↵
</spoiler>↵
↵
Warning: if you haven't participated in round 858 and want to do it virtually or just solve problems from there then I advice you not to read it because you may get spoilers.↵
↵
<spoiler summary="Problem">↵
...You are given an array of up to 500000 numbers which can be up to 10^30. Define the cost of the subset of the array as sum of elements of this subset plus gcd of elements of this subset. For every k from 1 to n print the maximum possible cost of some subset of size k. TL:8 sec. (By the way on the municipal stage there was only k=2).↵
</spoiler>↵
↵
