phong605's blog

Please help me to solve this problem
By phong605, 10 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      First I misunderstood problem satement. Comment was edited shortly after.

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your improvement decreases my estimate to O(log(n) * L) (using CRT)

    → Reply