Блог пользователя phong605

Please help me to solve this problem
Автор phong605, 10 лет назад, По-английски

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:

  1. (n, L, R, K) = (3, 0, 10, 1) => output: YES.

  2. (n, L, R, K) = (3, 0, 10, 21) => output: NO.

Limit:

  1. 3 ≤ n ≤ 105

  2. 0 ≤ L ≤ R ≤ 100.

  3. K ≤ 1030000.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

You can use chinese remainder theorem. Check all possible A and B. To calculate F[n] modulo P you can use matrix exponentation.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    BTW, instead of dealing with big integers you can use several random prime modulos. Very nice trick.

    → Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      CRT proves we can find an answer using modular arithmetic and some prime numbers with LCM greater than resulting integers.

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

→ Ответить