Malinovsky239

Untitled

Sep 25th, 2012
875
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <cassert>
  6. #include <complex>
  7. #include <cstdio>
  8. #include <vector>
  9. #include <cctype>
  10. #include <string>
  11. #include <ctime>
  12. #include <cmath>
  13. #include <set>
  14. #include <map>
  15.  
  16. typedef long double LD;
  17. typedef long long LL;
  18.  
  19. using namespace std;
  20.  
  21. #define sz(A) (int)(A).size()
  22. #define mp make_pair
  23. #define pb push_back
  24.  
  25. int m;
  26. vector<LL> dif_pos;
  27.  
  28. struct matr {
  29.     LL m[2][2];
  30. };
  31.  
  32. matr operator * (matr a, matr b) {
  33.     matr res;
  34.  
  35.     for (int i = 0; i < 2; i++)
  36.         for (int j = 0; j < 2; j++) {
  37.             res.m[i][j] = 0;
  38.             for (int k = 0; k < 2; k++) {
  39.                 res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % m;
  40.             }
  41.         }
  42.     return res;
  43. }
  44.  
  45. matr power(matr m, LL p) {
  46.     if (p == 1)
  47.         return m;
  48.     if (p % 2)
  49.         return m * power(m, p - 1);
  50.     return power(m * m, p / 2);
  51. }
  52.  
  53. int fib(LL num) {
  54.     if (num == 1)
  55.         return 1;
  56.     matr f;
  57.     f.m[0][0] = 0;
  58.     f.m[0][1] = f.m[1][0] = f.m[1][1] = 1;
  59.     f = power(f, num);
  60.     return f.m[0][1];
  61. }
  62.  
  63. int main() {
  64.     LL l, r, k;
  65.  
  66.     cin >> m >> l >> r >> k;
  67.  
  68.     if(m == 1){
  69.         cout << 0 << endl;
  70.         exit(0);
  71.     }
  72.  
  73.  
  74.     for (LL d = 1; d * d <= r; d++) {
  75.         LL d2 = r / d; 
  76.         dif_pos.pb(d);             
  77.         dif_pos.pb(d2);                    
  78.     }
  79.    
  80.     for (LL d = 1; d * d <= l; d++) {
  81.         if (l % d == 0)
  82.             dif_pos.pb(l / d);
  83.         else {
  84.             if (d) {
  85.                 dif_pos.pb(l / (d - 1));
  86.             }
  87.         }      
  88.     }
  89.  
  90.     LL ans = 0;
  91.  
  92.     for (int i = 0; i < sz(dif_pos); i++) {
  93.         LL d_b = l / dif_pos[i] + LL(l % dif_pos[i] != 0);
  94.         LL u_b = r / dif_pos[i];
  95.         if (u_b - d_b + 1 >= k)
  96.             ans = max(ans, dif_pos[i]);                
  97.     }
  98.     cout << fib(ans) << endl;
  99.  
  100.     return 0;
  101. }
RAW Paste Data