### PROBLEM LINKS

### DIFFICULTY

EASY

### EXPLANATION

Finding **x[k]** at each step directly by definition is very slow. Let’s do the following. After we find some **x[k]** let’s mark all numbers greater than **x[k]** that definitely can’t be the future elements of this sequence. What are these numbers? Clearly that all numbers of the form **a * x[i] - b * x[j]** where **1 <= i, j <= k** can’t be the elements of this sequence. But all other numbers possibly can belong to this sequence until we find the next element. The element **x[k]** bring us the following numbers that was not marked earlier: **a * x[k] - b * x[i] for 1 <=i <=k and a * x[i] - b * x[k] for 1 <=i < k**. So we need to mark only these **2 * k - 1** numbers at **k**th step. The finding of **x[k]** now becomes easy. We just need to iterate through all numbers greater than **x[k - 1]** until we find not marked number. This number is equal to **x[k]**.

Some additional hints. Don’t forget to mark **a - b** before finding **x 2 **. Take some bound for numbers that will be marked. We don’t need to mark numbers greater than **x[n]**. Of course we don’t know it. But we can estimate it. Since at each step we mark at most **2 * k - 1** new numbers it follows that **x[k+1] <= x[k] + 2 * k - 1**. And hence **x[n] <= 1 + 1 + 3 + 5 + … + (2 * n - 3) = (n - 1) ^{2} + 1**. Thus we can mark only numbers that is not greater than

**(n - 1)**. In fact you don’t need all this stuff and simply can mark all numbers using array with one million elements. Thus we obtain algorithm with complexity

^{2}+ 1**O(n**.

^{2})### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.