fork download 
  1. // e
  2.  
  3. // Author: _Sherbiny
  4.  
  5. #include "bits/stdc++.h"
  6. using namespace std;
  7. using ll = long long;
  8. #define endl '\n'
  9. #define int ll
  10. //====================//
  11.  
  12. const int mod = 1e9 + 7;
  13. int power(int a, int b) {
  14.     int res = 1;
  15.     while(b) {
  16.         if(b&1) res = 1ll * res * a % mod;
  17.         a = 1ll * a * a % mod, b >>= 1;
  18.     }
  19.     return res;
  20. }
  21.  
  22. // from 1 to n how many number contains the kth bit
  23. int count(int n, int k) {
  24.     ++n;
  25.     int d = 1LL << k + 1, p = 1LL << k;
  26.     return n / d * p + max(0LL, n % d - p);
  27. }
  28.  
  29. void magic() {
  30.     int n; cin >> n;
  31.  
  32.     int ans = 0;
  33.     for(int i = 0; i < 32; ++i) {
  34.         int has = count(n, i);
  35.         ans += has * (n - has) * 2 % mod * (1ll << i) % mod;
  36.         ans %= mod;
  37.     }
  38.  
  39.     cout << ans * power(n, mod - 2) % mod << endl;
  40. }
  41.  
  42. signed main() {
  43.     ios_base::sync_with_stdio(0);
  44.     cin.tie(0), cout.tie(0);
  45.  
  46.     int t = 1;
  47.     cin >> t;
  48.     while (t--) magic();
  49. }
  50.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/vsbVW7
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!