fork download
copy 
  1.  
  2.     #include <bits/stdc++.h>
  3.  
  4.     using namespace std;
  5.  
  6.     using ll = long long;
  7.     const int MOD = 1000000007; 
  8.     const int MOD2 =  998244353; 
  9.     const ll INF = 1e18;
  10.     const int MX = 1000001; //check the limits, dummy
  11.  
  12.  
  13.     ll modExp(ll base, ll power) {
  14.         if (power == 0) {
  15.             return 1;
  16.         } else {
  17.             ll cur = modExp(base, power / 2); cur = cur * cur; cur = cur % MOD;
  18.             if (power % 2 == 1) cur = cur * base;
  19.             cur = cur % MOD;
  20.             return cur;
  21.         }
  22.     }
  23.  
  24.     ll inv(ll base) {
  25.         return modExp(base, MOD-2);
  26.     }
  27.  
  28.  
  29.     ll mul(ll A, ll B) {
  30.         return (A*B)%MOD;
  31.     }
  32.  
  33.     ll add(ll A, ll B) {
  34.         return (A+B)%MOD;
  35.     }
  36.  
  37.     ll dvd(ll A, ll B) {
  38.         return mul(A, inv(B));
  39.     }
  40.  
  41.     ll sub(ll A, ll B) {
  42.         return (A-B+MOD)%MOD;
  43.     }
  44.  
  45.     ll* facs = new ll[MX];
  46.     ll* facInvs = new ll[MX];
  47.  
  48.     ll choose(ll a, ll b) {
  49.         if (b > a) return 0;
  50.         if (a < 0) return 0;
  51.         if (b < 0) return 0;
  52.         ll cur = facs[a];
  53.         cur = mul(cur, facInvs[b]);
  54.         cur = mul(cur, facInvs[a-b]);
  55.         return cur;
  56.     }
  57.  
  58.  
  59.     void initFacs() {
  60.         facs[0] = 1; 
  61.         facInvs[0] = 1;
  62.         for (int i = 1 ; i < MX ; i ++ ) {
  63.             facs[i] = (facs[i-1] * i) % MOD;
  64.             facInvs[i] = inv(facs[i]);
  65.         }
  66.     }
  67.     long long computeLucky(long long n, long long k) {
  68.         // We'll accumulate twice the true answer into ans2,
  69.         // so we can avoid worrying about (n+1)/2 being fractional when n is even.
  70.         long long ans2 = 0;
  71.  
  72.         // segments = 2^i, length = L_i
  73.         long long segments = 1;
  74.         long long length   = n;
  75.  
  76.         // Walk down levels until segments would be shorter than k:
  77.         while (length >= k) {
  78.             if (length % 2 == 1) {
  79.                 // This level is odd-length → add segments * (n+1)
  80.                 ans2 += segments * (n + 1);
  81.             }
  82.             // split every segment in half for next level
  83.             length   /= 2;
  84.             segments *= 2;
  85.         }
  86.  
  87.         // Divide by 2 to get the real sum of midpoints
  88.         return ans2 / 2;
  89.     }
  90.  
  91.     int main()  {
  92.         ios_base::sync_with_stdio(0); cin.tie(0);  
  93.         int T;
  94.         cin >> T;
  95.         while (T--) {
  96.             long long n, k;
  97.             cin >> n >> k;
  98.             cout << computeLucky(n, k) << "\n";
  99.         }
  100.  
  101.  
  102.  
  103.         return 0;
  104.     }
  105.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
6
7 2
11 3
55 13
5801 6
8919 64
8765432 1
stdout
copy 
12
18
196
1975581
958900
38416403456028
https://ideone.com/nKHemL
language:
C++ (gcc 8.3)
created:
17 hours 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!