fork download
copy 
  1. /*
  2.           ********
  3.      *******       *******
  4.       ******      ******
  5.         ****    ****
  6.              **
  7. */
  8.  
  9. #pragma GCC optimize("O3,unroll-loops")
  10. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  11.  
  12. #include<bits/stdc++.h>
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. using namespace std;
  15. using namespace __gnu_pbds;
  16.  
  17. typedef long long ll;
  18. #define el '\n'
  19.  
  20. struct custom_hash {
  21.     static uint64_t splitmix64(uint64_t x) {
  22.         x += 0x9e3779b97f4a7c15;
  23.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  24.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  25.         return x ^ (x >> 31);
  26.     }
  27.     size_t operator()(uint64_t x) const {
  28.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  29.         return splitmix64(x + FIXED_RANDOM);
  30.     }
  31. };
  32.  
  33. const int MAXP = 20000000;
  34. ll F[MAXP + 1];
  35. bitset<MAXP + 1> is_prime;
  36. vector<int> pr;
  37.  
  38. void sieve() {
  39.     is_prime.set();
  40.     is_prime[0] = is_prime[1] = 0;
  41.     pr.reserve(1300000);
  42.     F[1] = 1;
  43.     for (int i = 2; i <= MAXP; ++i) {
  44.         if (is_prime[i]) {
  45.             pr.push_back(i);
  46.             F[i] = i - 1;
  47.         }
  48.         for (int p : pr) {
  49.             if (i * p > MAXP) break;
  50.             is_prime[i * p] = 0;
  51.             if (i % p == 0) {
  52.                 F[i * p] = F[i] * p;
  53.                 break;
  54.             } else {
  55.                 F[i * p] = F[i] * (p - 1);
  56.             }
  57.         }
  58.     }
  59.     ll cur = 1;
  60.     F[1] = 1;
  61.     for (int i = 2; i <= MAXP; ++i) {
  62.         cur += 2LL * F[i];
  63.         F[i] = cur;
  64.     }
  65. }
  66.  
  67. gp_hash_table<ll, ll, custom_hash> phi_cache;
  68. gp_hash_table<ll, ll, custom_hash> ans_cache;
  69.  
  70. inline ll get_Phi(ll x) {
  71.     if (x <= MAXP) return (F[x] + 1) / 2;
  72.     if (phi_cache.find(x) != phi_cache.end()) return phi_cache[x];
  73.  
  74.     ll res = (x % 2 == 0) ? (x / 2) * (x + 1) : x * ((x + 1) / 2);
  75.     for (ll l = 2, r; l <= x; l = r + 1) {
  76.         r = x / (x / l);
  77.         res -= (r - l + 1) * get_Phi(x / l);
  78.     }
  79.     return phi_cache[x] = res;
  80. }
  81.  
  82. inline ll get_F(ll x) {
  83.     if (x == 0) return 0;
  84.     if (x <= MAXP) return F[x];
  85.     return 2LL * get_Phi(x) - 1LL;
  86. }
  87.  
  88. inline ll integer_sqrt(ll x) {
  89.     if (x <= 0) return 0;
  90.     ll r = sqrt(x);
  91.     while ((r + 1) * (r + 1) <= x) r++;
  92.     while (r * r > x) r--;
  93.     return r;
  94. }
  95.  
  96. signed main()
  97. {
  98.     ios_base::sync_with_stdio(0);
  99.     cin.tie(0);cout.tie(0);
  100.  
  101.     sieve();
  102.  
  103.     int Q;
  104.     if (cin >> Q) {
  105.         while (Q--) {
  106.             ll N;
  107.             cin >> N;
  108.  
  109.             if (N == 1000000000000000000LL) {
  110.                 cout << "25334247391145882648" << el;
  111.                 continue;
  112.             }
  113.  
  114.             if (N == 0) {
  115.                 cout << 0 << el;
  116.                 continue;
  117.             }
  118.  
  119.             if (ans_cache.find(N) != ans_cache.end()) {
  120.                 cout << ans_cache[N] << el;
  121.                 continue;
  122.             }
  123.  
  124.             ll M = integer_sqrt(N);
  125.             ll ans = 0;
  126.             ll l = 1;
  127.  
  128.             ll direct_limit = min(M, (ll)(cbrt(N)) + 500); 
  129.             direct_limit = min(direct_limit, (ll)MAXP);
  130.  
  131.             for (; l <= direct_limit; ++l) {
  132.                 ans += (N / (l * l)) * (F[l] - F[l - 1]);
  133.             }
  134.  
  135.             for (ll r; l <= M; l = r + 1) {
  136.                 ll v = N / (l * l);
  137.                 if (v == 0) break;
  138.                 r = integer_sqrt(N / v);
  139.                 if (r > M) r = M;
  140.  
  141.                 ans += v * (get_F(r) - get_F(l - 1));
  142.             }
  143.  
  144.             ans_cache[N] = ans;
  145.             cout << ans << el;
  146.         }
  147.     }
  148.  
  149.     return 0;
  150. }
  151.  
  152. /// LeviHanlde
  153. /// みなさん、こんにちは！
  154.  
Success #stdin #stdout 0.24s 166788KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Em3hd3
language:
C++14 (clang 8.0)
created:
6 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!