Ngày 12-1-2019 - Bài 3

GCDFIB - Ước chung lớn nhất của dãy fibonacci

Dữ liệu vào: standard input

Dữ liệu ra: standard output

Giới hạn thời gian: 1.0 giây

Giới hạn bộ nhớ: 256 megabyte

Đăng bởi: namnguyen123

Dãy số fibonacci được quy ước như sau : 

           F₁ = 1 , F₂ = 1 , F_n  = F_{n - 1}  + F_{n - 2} ( n > 3) . 

 

Cho tập A =  { F_L , F_{L + 1}  , ... , F_R  } (Với F_i  là số fibonacci thứ i ) .

 

Yêu cầu : Hãy xác đinh giá trị lớn nhất của UCLN của các phần tử tập S là tập con của A có đúng K phần tử.

 

Kết quả : Lấy phần dư khi chia kết quả cho MOD . 

 

Input : 

• Gồm 1 dòng chứa các số nguyên dương MOD , L , R , K
• ( 1  <  MOD  < 10⁹  ;  1  <  L  <  R  < 10¹²  ;  1 <  K  <  R - L + 1 ).

Output :

• Kết quả lấy dư khi chia cho MOD.

 

  

  

Ví dụ

• input
  10 1 8 2
  output
  3
• input
  10 1 8 3
  output
  1

8 số đầu là 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21

Nếu k = 2 thì kết quả là 3 vì UCLN của tập {3 , 21} là 3 là số lớn nhất .

Nếu k = 3 thì kết quả là 1 vì UCLN các tập có độ dài 3 đều có UCLN là 1 .

Lời giải:

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
#define long long long

long mod, l, r, k;
map<long, long> f;

bool check(long i) {
    return (r / i - (l - 1) / i >= k);
}

long getF(long n) {
    if (f.count(n)) return f[n];
    long k = n / 2;
    if (n % 2 == 0) return (f[n] = (getF(k) * getF(k) + getF(k - 1) * getF(k - 1)) % mod);
    return (f[n] = (getF(k) * getF(k + 1) + getF(k - 1) * getF(k)) % mod);
}

int main() {
    cin >> mod >> l >> r >> k;
    long id = 0;
    for (long i = 1; i * i <= r; ++i) {
        if (check(i)) id = max(id, i);
        if (check(r / i)) id = max(id, r / i);
    }
    f[0] = f[1] = 1;
    cout << getF(id - 1);
    return 0;
}