fork download
copy 
  1. // i am monkey
  2. #pragma GCC optimize("O2,unroll-loops")
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. // #include "bits/extc++.h"
  6. // using namespace __gnu_pbds;
  7.  
  8.  
  9. using ll = long long;
  10. using ld = long double;
  11. using vi = vector<int>;
  12. using vl = vector<ll>;
  13. using vd = vector<ld>;
  14. using pi = pair<int, int>;
  15. using pl = pair<ll, ll>;
  16. using pd = pair<ld, ld>;
  17. // template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  18. template<class T> using uset = unordered_set<T>;
  19. template<class K, class V> using umap = unordered_map<K, V>;
  20. inline void fastio() {ios_base::sync_with_stdio(false); cin.tie(NULL);}
  21. inline void precision(int k) {cout << fixed << setprecision(k);}
  22. #define iter(x) (x).begin(), (x).end()
  23. #define _f first
  24. #define _s second
  25. const char nl   = '\n';
  26. const int  INF  = (1 << 30) - 1;
  27. const ll   LINF = 1e18;
  28. const ld   PI   = 3.14159265358979323846L;
  29. const ld   E    = 2.71828182845904523536L;
  30. const ld   eps  = 1e-7;
  31. #define debug
  32. #ifdef debug
  33. #define dbx(x) cout << x << endl;
  34. #define dbn(x) cout << x << nl;
  35. #define dba(x) cout << x << " ";
  36. #else
  37. #define dbx(x) ;
  38. #define dbn(x) ;
  39. #define dba(x) ;
  40. #endif
  41.  
  42.  
  43.  
  44. ll n; int m, l;
  45. ll per[55];
  46. ll solve(ll n, int m, bool sub_m){
  47.     if(!n) return 0;
  48.     if(n <= m && sub_m) return 1;
  49.     ll res = 0;
  50.     if(sub_m){
  51.         n -= m;
  52.         res++;
  53.     }
  54.     for(int i = m; i >= 1; i--){
  55.         res += (1ll << (i - 1)) * (n / per[i]);
  56.         n %= per[i];
  57.         if(n > per[i] - i){
  58.             n = per[i] - i;
  59.             res++;
  60.         }
  61.     }
  62.     return res;
  63. }
  64. int main(){
  65.     fastio(); precision(15);
  66.     cin >> n >> m >> l;
  67.     if(!l) l = m;
  68.     per[1] = 1;
  69.     for(int i = 2; i <= m; i++){
  70.         for(int j = 1; j < i; j++) per[i] += per[j];
  71.         per[i] += i;
  72.     }
  73.     ll k = (1ll << l) - 2;
  74.     ll ans;
  75.     if(n > k){
  76.         ans = solve(k, m - 1, 0) + solve(n - k, m, 1);
  77.         if(l != 1) ans--;
  78.     }else{
  79.         ans = solve(n, l - 1, 1) - 1;
  80.     }
  81.     // dbn(ans);
  82.     if(!ans){
  83.         cout << "0 1\n";
  84.         exit(0);
  85.     }
  86.     ll g = __gcd(ans, n);
  87.     ans /= g;
  88.     n /= g;
  89.     cout << ans << ' ' << n << nl;
  90. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
7 2 1
stdout
copy 
5 7
https://ideone.com/vajtXA
language:
C++ (gcc 8.3)
created:
2 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!