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 : 
           F1 = 1 , F= 1 , Fn  = Fn - 1  + Fn - 2 ( n > 3) . 
 
Cho tập A =  { F, FL + 1  , ... , F } (Với Fi  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  < 109  ;  1  <  L  <  R  < 1012  ;  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 .

Back to Top