Editorial for COCI '12 Contest 1 #5 Snaga

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

An important observation is that, for any large $N$ ~N~, the following number in the sequence – the smallest positive integer that doesn't divide it – is very small. Thus, there are very few possible numbers following any large number, hence it is natural to approach the problem as follows: for each of the possible followers $K$ ~K~ we can count the numbers between $A$ ~A~ and $B$ ~B~ followed by $K$ ~K~, making it easy to compute the sum of their strengths – they all have a strength of $\text{strength}(K)+1$ ~\text{strength}(K)+1~.

How can we count the numbers for a given $K$ ~K~? What are the conditions for a number $N$ ~N~ to be followed by $K$ ~K~? It has to be divisible by all numbers less than $K$ ~K~ (otherwise one of them would be the follower of $N$ ~N~), which means it is also divisible by their least common multiple, $\operatorname{lcm}(1, 2, \dots, K-1)$ ~\operatorname{lcm}(1, 2, \dots, K-1)~. Furthermore, it must not be divisible by $K$ ~K~ itself. These two conditions are obviously both necessary and sufficient.

Thus, let us count the numbers between $A$ ~A~ and $B$ ~B~ divisible by $\operatorname{lcm}(1, 2, \dots, K-1)$ ~\operatorname{lcm}(1, 2, \dots, K-1)~. From that number, we need to subtract the numbers divisible by $K$ ~K~. The numbers in the intersection of the two sets (divisible by both $\operatorname{lcm}(1, 2, \dots, K-1)$ ~\operatorname{lcm}(1, 2, \dots, K-1)~ and $K$ ~K~) are also divisible by $\operatorname{lcm}(1, 2, \dots, K-1, K)$ , so it is easy to find and subtract their count between $A$ ~A~ and $B$ ~B~. Generally, we can count the numbers between $A$ ~A~ and $B$ ~B~ (inclusive) divisible by $D$ ~D~ using the formula (think about why it is correct): $B \mathbin{div} D - (A-1) \mathbin{div} D$ .

Finally, for which numbers $K$ ~K~ do we need to carry out the computation? From the discussion above, it is obvious that as soon as $\operatorname{lcm}(1, 2, \dots, K-1)$ ~\operatorname{lcm}(1, 2, \dots, K-1)~ becomes greater than $B$ ~B~, we are done: there are no numbers between $A$ ~A~ and $B$ ~B~ with such (or any greater) $K$ ~K~ (since they aren't divisible by $\operatorname{lcm}(1, 2, \dots, K-1)$ ~\operatorname{lcm}(1, 2, \dots, K-1)~, being smaller than it). It turns out that the largest $K$ ~K~ will be less than $50$ ~50~. It is easy to compute the strength for such $K$ ~K~, increment it by $1$ ~1~ and add it to the total sum as many times as there are numbers between $A$ ~A~ and $B$ ~B~ whose follower is $K$ ~K~.

The last thing to consider is calculating $\operatorname{lcm}(1, 2, \dots, K-1, K)$ . Notice that

$\displaystyle \operatorname{lcm}(1, 2, \dots, K-1, K) = \operatorname{lcm}(\operatorname{lcm}(1, 2, \dots, K-1), K)$

so if we have calculated $V = \operatorname{lcm}(1, 2, \dots, K-1)$ in the previous step, then $\operatorname{lcm}(V, K)$ ~\operatorname{lcm}(V, K)~ can be obtained using the formula $V \times K / \gcd(V, K)$ ~V \times K / \gcd(V, K)~, which is valid for any two positive integers. $\gcd$ ~\gcd~, the greatest common divisor, is easily obtained using Euclid's algorithm.

Comments

There are no comments at the moment.