### 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 - 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:

*- b * x[k] for 1 <=i < k**. So we need to mark only these*

*a * x[k] - b * x*for 1 <=i <=k and a * x**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.