# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* harsh_h

*mexomerf*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

Binary search

# PROBLEM:

A sequence X is defined as:

- X_1 = 0, X_2 = A, X_3 = B
- X_i = X_{i-1} + X_{i-2} - X_{i-3} for i \gt 3.

Find the K'th smallest element of this sequence.

# EXPLANATION:

Let’s look at a few further terms of the sequence

We see something of a pattern here: the odd terms are of the form A+x\cdot B, while the even terms are of the form x\cdot B.

This does indeed hold.

## Proof

We use induction.

Our claim is that:

This is of course true for X_1, X_2, X_3, which will be our base cases.

Let’s look at further indices.

Suppose N = 2i where N\gt 3. Then,

Similarly, if N = 2i+1 and N \gt 3, we have

This proves our claims.

Let’s use this to find the K'th smallest element.

The even and odd terms are individually simple enough - they start at A or 0 respectively, and then keep increasing by B, forming an arithmetic progression.

This allows us to binary search for the answer.

That is, consider the function f(x) = number of elements in the sequence that are \leq x.

We’ll find the smallest x such that f(x) \geq K: that will be our answer.

To compute f(x), we look at the even and odd terms separately.

- The odd terms are 0, B, 2B, 3B, \ldots

n\cdot B \leq x if and only if n \leq \frac{x}{B}.

So, we want to count the number of non-negative integers that are \leq \frac{x}{B}.

This is exactly

- The even terms are A, A+B, A+2B, \ldots

A+n\cdot B \leq x if and only if n \leq \frac{x-A}{B}

Again, the count of such n is

\left\lfloor \ \cdot\ \right\rfloor here is the floor function.

Note that in the second case, if x \lt A then the count of valid n is in fact 0 - make sure to take care of that correctly.

Now that a single f(x) can be computed in \mathcal{O}(1) time, we simply use binary search to find the answer.

The only remaining thing to think about is the initial bounds of the binary search.

The lower bound is clearly 0, since X_1 = 0.

As for the upper bound: a simple upper bound is K\cdot B, which for our constraints is \leq 10^{18}.

So, you can safely always choose 10^{18} as an upper bound.

A slightly more strict upper bound on the answer is A + \frac{K}{2}\cdot B.

It is also possible to further exploit the pattern and solve this problem in constant time with a bit of casework, which can be seen in the tester’s solution below.

# TIME COMPLEXITY:

\mathcal{O}(\log (A+K\cdot B)) per testcase.

# CODE:

## Tester's code (C++)

```
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int t;
cin>>t;
while(t--){
int a, b, k;
cin>>a>>b>>k;
int temp = (a / b);
if(k <= temp + 1){
cout<<(k - 1) * b<<"\n";
}else{
if(k % 2 == temp % 2){
cout<<a + ((k - temp - 1) / 2) * b<<"\n";
}else{
cout<<(temp + ((k - temp) / 2)) * b<<"\n";
}
}
}
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
a, b, k = map(int, input().split())
lo, hi = 0, 10**18
while lo < hi:
mid = (lo + hi)//2
# 0, a, b, a+b, 2b, a+2b, 3b, a+3b, ...
# odd terms: x*b
# even terms a + x*b
# odd terms: x*b <= mid -> x <= floor(mid/b)
ct = mid//b + 1
# even terms: a + x*b <= mid -> x <= floor((mid-a)/b)
if a <= mid: ct += (mid-a)//b + 1
if ct >= k: hi = mid
else: lo = mid+1
print(lo)
```