We define F sequence: F1 = a, F2 = b, Fi = Fi - 1 + Fi - 2 (3 ≤ i). You are given 4 positive integer n, L, R, K. Your task is check whether there exist two integer a, b that L ≤ a, b ≤ R and Fn = K.
Example:
(n, L, R, K) = (3, 0, 10, 1) => output: YES.
(n, L, R, K) = (3, 0, 10, 21) => output: NO.
Limit:
3 ≤ n ≤ 105
0 ≤ L ≤ R ≤ 100.
K ≤ 1030000.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
You can use chinese remainder theorem. Check all possible A and B. To calculate F[n] modulo P you can use matrix exponentation.
BTW, instead of dealing with big integers you can use several random prime modulos. Very nice trick.
First I misunderstood problem satement. Comment was edited shortly after.
Thank goo.gl_SsAhv. But I don't know that I used Chinese remainder theorem for what? I think we just need using matrix exponentation to solve.
Ok. let's denote by L number of digits in number K. It can be up to 30000. To multiply two matrices you have to multiply two big numbers. It results in O(L^2) number of operations to multiply two numbers. To calculate F[n] using matrix exponentation O(Log(n) * L^2). Use CRT to reduce complexity to O(log(n) * L). We can select some set P of prime numbers. Product of all numbers in P has to be greater than F[n] and greater than K. To multiply two numbers we need just one cicle
(A * B).x[i] = A.x[i] * B.x[i] % p[i];UPD: By the way, we have to check all possible pairs A and B, so multiply estimates above by 100^2. It's better to perform exponentation separetely for each prime one by one.
Sorry, but how to use CRT? It seems that there is no modulus here. IMHO, solution should be the same but with big integers instead of CRT.
CRT proves we can find an answer using modular arithmetic and some
primenumbers with LCM greater than resulting integers.What I said above is that it must be enough to use very few random prime numbers, even if their LCM is less than the number K. The probability of collision will be quite low.
There is one another solution. Let f[n] be usual Fibonacci numbers: f[1] = 1, f[2] = 2, f[n] = f[n-1] + f[n-2]. One can prove that F[n] = f[j] * F[n-j] + f[j-1] * F[n-j-1]. So, F[n] = f[n-2] * F[2] + f[n-3] * F[1] = f[n-2] * b + f[n-3] * a. From this point you just need to solve equation: a*f[n-3] + b*f[n-2] = K in domain L<=a,b<=R. You can calculate Fibonacci numbers using matrix exponentation or smth like this and then try all pairs (a,b).
Your improvement decreases my estimate to O(log(n) * L) (using CRT)