fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long 
  4. #define el cout << '\n'
  5. #define BIT(n) ((1ll) << (n))
  6. #define bit(mask, i) (((mask) >> (i)) & 1)
  7.  
  8. using namespace std;
  9.  
  10. const int MOD = 1e9 + 7;
  11.  
  12. int t, n, m;
  13.  
  14. ll binpow(ll a, ll b)
  15. {
  16.     ll ans = 1;
  17.     for (; b; b >>= 1, (a *= a) %= MOD)
  18.         if (b & 1)
  19.             (ans *= a) %= MOD;
  20.     return ans;
  21. }
  22.  
  23. int main()
  24. {
  25.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  26.     if (fopen("COUNTSEQ.INP", "r"))
  27.     {
  28.         freopen("COUNTSEQ.INP", "r", stdin);
  29.         freopen("COUNTSEQ.OUT", "w", stdout);
  30.     }
  31.  
  32.     cin >> t;
  33.     while (t--)
  34.     {
  35.         ll ans = 0;
  36.         vector<int> p;
  37.         cin >> n;
  38.         m = n;
  39.         for (ll i = 2; i * i <= n; i++)
  40.         {
  41.             bool flag = 0;
  42.             while (m % i == 0)
  43.             {
  44.                 m /= i;
  45.                 flag = 1;
  46.             }
  47.             if (flag)
  48.                 p.push_back(i);
  49.         }
  50.         if (m > 1)
  51.             p.push_back(m);
  52.         for (int mask = 0; mask < BIT(p.size()); mask++)
  53.         {
  54.             ll mul = 1;
  55.             for (int i = 0; i < p.size(); i++)
  56.                 if (bit(mask, i))
  57.                     mul *= p[i];
  58.             if (__builtin_popcount(mask) & 1)
  59.                 (ans -= binpow(2, n/mul - 1)) %= MOD;
  60.             else
  61.                 (ans += binpow(2, n/mul - 1)) %= MOD;
  62.         }
  63.         cout << (ans + MOD) % MOD, el;
  64.     }
  65. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YC6R0z
language:
C++14 (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!