# PROBLEM LINKS

Practice

Contest

# 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)**^{2} + 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 **O(n**^{2}).

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

asked
**22 Nov '12, 18:48**

0★admin ♦♦

19.8k●350●498●541

accept rate:
36%

sir, can you please tell what is wrong with my solution. I feel that it is according to the editorial but I am getting wrong answer. Thanks.