fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
  5. #define ROF(i, a, b) for (auto i = (a); i >= (b); --i)
  6. #define sz(x) (int)(x).size()
  7. #define pb push_back
  8. #define ppb pop_back
  9. #define endl '\n'
  10. #define fi first
  11. #define se second
  12.  
  13. #ifdef Juhan404
  14. #include "debug.h"
  15. #else
  16. #define debug(...)
  17. #endif
  18.  
  19. using ll = long long;
  20. using pii = pair<int, int>;
  21.  
  22. const int MOD = 1e9 + 7;
  23. const int N = 1e5 + 5;
  24.  
  25. ll n, k, F[50], X[50];
  26.  
  27. void prepare() {
  28.     F[0] = 1, F[1] = 1;
  29.     FOR(i, 2, 49) {
  30.         F[i] = F[i - 1] + F[i - 2];
  31.     }
  32.  
  33.     X[0] = 1, X[1] = 0;
  34.     FOR(i, 2, 49) {
  35.         X[i] = X[i - 1] + X[i - 2];
  36.     }
  37. }
  38.  
  39. ll Find(ll n, ll k) {
  40.     if (k == F[n])
  41.         return X[n];
  42.  
  43.     if (k >= F[n - 1])
  44.         return X[n - 1] + Find(n - 2, k - F[n - 1]);
  45.     else
  46.         return Find(n - 1, k);
  47. }
  48.  
  49. void run_case() {
  50.     cin >> n >> k;
  51.  
  52.     cout << Find(n, k) << endl;
  53. }
  54.  
  55. int main() {
  56.     cin.tie(0)->sync_with_stdio(0);
  57.  
  58. #ifdef Juhan404
  59.     freopen("Error.txt", "w", stderr);
  60. #endif
  61.  
  62.     int T = 1;
  63.     cin >> T;
  64.  
  65.     prepare();
  66.  
  67.     for (int test = 1; test <= T; ++test) {
  68.  
  69.         run_case();
  70.     }
  71.     return 0;
  72. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
1
5 0
stdout
copy 
23169589761472
https://ideone.com/VdVt2p
language:
C++14 (gcc 8.3)
created:
30 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!