| From organizers: "Algorithmic Engagements is the biggest Polish programming contest with about 2000 competitors every year. It consists of 6 online elimination rounds, after which top 20 contestants advance to an onsite final, held in Zielona Góra or Warsaw, Poland. |
| This year we’ve decided to hold an online, open contest in parallel to the onsite finals." |
Date: 26.11.2011
You can read about that contest and register here: http://contest.mimuw.edu.pl/
Can anybody tell simple simple solutions to egz and bio?
In egz I understand how to solve it with 2d-segment tree, but is there something easier?
I don't know whether it's the most simple solution. Moreover, I think it's not, but that's how I solved:
First of all, let's generate all prime numbers up to 3000000. Using that we can factorise numbers in O(sqrt(n)/log(n)) time.
Lets add by one. While adding number Ai we will add to the answer number of Aj(j < i), that are coprime with Ai. Let B[p] is number of Aj that p|Aj. Let's factorise Ai. Let p1, p2...pm be the primes that divide Ai Number of Aj that are not coprime with Ai is number of Aj that one of p1, p2...pm divides Aj. Which is equal (using inclusion-exclusion formula) to B[p1] + B[p2] + ... + B[pm] - B[p1 * p2] - ... - B[pm - 1 * pm] + ... ± B[p1 * p2 * ... * pm].
After adding Ai we need to update B, using p1, ...pm.
Complexity - O(n * (sqrt(max) / log(max)+ 2m)), where m is the maximum possible number of primes in factorisation of the number <= 3000000, equal to 7 (in number 2 * 3 * 5 * 7 * 11 * 13 * 17 = 510510).
This works at about 2 second on my computer on maxtest.