Author: Anton Trygub
Solved by:
First to solve: Insight
Let's consider arcs between the numbers and .
First observation: , , , for any , so the conditions involving and are automatically satisfied and we can forget about them.
Second observation: in each arc the numbers are strictly decreasing (if 2<x<y on some arc, we get x\text{ mod }y = x>2, contradiction).
Now, we need to do a sieve-like dp. Let denote the number of ways to split the numbers from to into arcs so that goes to the first arc and x+1 goes to the second. We can calculate this dp for each from to in the following manner: suppose that the numbers x+1,\ldots, k go to the second arc while k+1 goes to the first one. Then we must have (k+1)\text{ mod }x \leq 2, and the number of such is \le 3\frac{n}{x}. As the sum of \frac{n}{x} over all is O(n\log(n)), we get O(n\log(n)) solution overall.