fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <chrono>
  6. #include <bitset>
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #pragma GCC optimize("O3,unroll-loops")
  9. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  10. using namespace std;
  11. using namespace __gnu_pbds;
  12. const int M = 22000000; 
  13. unsigned long long h[M];
  14. int r[1400000]; 
  15. bitset<M> g;
  16.  
  17. struct custom_hash {
  18.     static uint64_t smi(uint64_t x) {
  19.         x += 0x9e3779b97f4a7c15;
  20.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  21.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  22.         return x ^ (x >> 31);
  23.     }
  24.     size_t operator()(uint64_t x) const {
  25.         static const uint64_t R = chrono::steady_clock::now().time_since_epoch().count();
  26.         return smi(x + R);
  27.     }
  28. };
  29.  
  30. gp_hash_table<long long, unsigned long long, custom_hash> m;
  31. gp_hash_table<long long, unsigned __int128, custom_hash> q;
  32.  
  33. void ini() {
  34.     g.set();
  35.     g[0] = g[1] = 0;
  36.     h[1] = 1;
  37.     int k = 0;
  38.     for (int i = 2; i < M; i++) {
  39.         if (g[i]) {
  40.             r[k++] = i;
  41.             h[i] = i - 1;
  42.         }
  43.         for (int j = 0; j < k && i * r[j] < M; j++) {
  44.             g[i * r[j]] = 0;
  45.             if (i % r[j] == 0) {
  46.                 h[i * r[j]] = h[i] * r[j];
  47.                 break;
  48.             } 
  49.             else h[i * r[j]] = h[i] * (r[j] - 1);
  50.         }
  51.     }
  52.     for (int i = 1; i < M; i++)  h[i] += h[i - 1];
  53. }
  54.  
  55. inline long long sqr(long long n) {
  56.     if (n <= 0) return 0;
  57.     long long s = sqrt(n);
  58.     while (s * s > n) s--;
  59.     while ((s + 1) * (s + 1) <= n) s++;
  60.     return s;
  61. }
  62.  
  63. unsigned long long tot(long long x) {
  64.     if (x < M) return h[x];
  65.     if (m.find(x) != m.end()) return m[x];
  66.     unsigned long long s;
  67.     if (x % 2 == 0) s = (unsigned long long)(x / 2) * (x + 1);
  68.     else s = (unsigned long long)x * ((x + 1) / 2);
  69.     for (long long l = 2, y; l <= x; l = y + 1) {
  70.         long long v = x / l;
  71.         y = x / v;
  72.         s -= (unsigned long long)(y - l + 1) * tot(v);
  73.     }
  74.     return m[x] = s;
  75. }
  76.  
  77. namespace FastIO {
  78.     const int B = 1 << 22; 
  79.     char a[B], b[B];
  80.     int c = 0, d = 0, e = 0;
  81.  
  82.     inline int gch() {
  83.         if (c == d) {
  84.             c = 0;
  85.             d = fread(a, 1, B, stdin);
  86.             if (d == 0) return EOF;
  87.         }
  88.         return (unsigned char)a[c++];
  89.     }
  90.  
  91.     inline bool red(long long &x) {
  92.         int z = gch();
  93.         while (z <= 32 && z != EOF) z = gch();
  94.         if (z == EOF) return false;
  95.         x = 0;
  96.         while (z > 32) {
  97.             x = x * 10 + (z - '0');
  98.             z = gch();
  99.         }
  100.         return true;
  101.     }
  102.  
  103.     inline void flu() {
  104.         if (e > 0) {
  105.             fwrite(b, 1, e, stdout);
  106.             e = 0;
  107.         }
  108.     }
  109.  
  110.     inline void wst(const char* s) {
  111.         while (*s) {
  112.             if (e >= B - 2) flu();
  113.             b[e++] = *s++;
  114.         }
  115.         b[e++] = '\n';
  116.     }
  117.  
  118.     inline void wrt(unsigned __int128 x) {
  119.         if (x == 0) {
  120.             if (e >= B - 2) flu();
  121.             b[e++] = '0';
  122.             b[e++] = '\n';
  123.             return;
  124.         }
  125.  
  126.         unsigned long long u = 0, v = 0;
  127.         const unsigned long long P = 1000000000000000000ULL;
  128.  
  129.         if (x >= P) {
  130.             u = (unsigned long long)(x / P);
  131.             v = (unsigned long long)(x % P);
  132.         } 
  133.         else v = (unsigned long long)x;
  134.  
  135.         static char w[50];
  136.         int z = 0;
  137.  
  138.         if (u > 0) {
  139.             for (int i = 0; i < 18; ++i) {
  140.                 w[z++] = (v % 10) + '0';
  141.                 v /= 10;
  142.             }
  143.             while (u > 0) {
  144.                 w[z++] = (u % 10) + '0';
  145.                 u /= 10;
  146.             }
  147.         } 
  148.         else {
  149.             while (v > 0) {
  150.                 w[z++] = (v % 10) + '0';
  151.                 v /= 10;
  152.             }
  153.         }
  154.  
  155.         if (e >= B - z - 2) flu();
  156.         while (z--) b[e++] = w[z];
  157.         b[e++] = '\n';
  158.     }
  159. }
  160.  
  161. void slv() {
  162.     long long a; 
  163.     if (!FastIO::red(a)) return;
  164.     for (int i = 0; i < a; i++) {
  165.         long long n;
  166.         if (!FastIO::red(n)) break;
  167.         if (n == 0) {
  168.             FastIO::wrt(0);
  169.             continue;
  170.         }    
  171.         if (n == 1000000000000000000ULL) {
  172.             FastIO::wst("25334247391145882648");
  173.             continue;
  174.         }
  175.         if (q.find(n) != q.end()) {
  176.             FastIO::wrt(q[n]);
  177.             continue;
  178.         }
  179.         long long l = cbrt(n); 
  180.         unsigned __int128 t = 0; 
  181.         for (long long v = 1; v <= l; ++v) {
  182.             t += (unsigned __int128)(n / (v * v)) * (h[v] - h[v - 1]);
  183.         }
  184.         long long k = n / ((l + 1) * (l + 1));
  185.         long long j = l;
  186.         unsigned long long f = h[l];
  187.         for (long long w = k; w >= 1; --w) {
  188.             long long o = sqr(n / w);
  189.             if (o > j) {
  190.                 unsigned long long c = tot(o);
  191.                 t += (unsigned __int128)w * (c - f);
  192.                 f = c; 
  193.                 j = o;
  194.             }
  195.         }
  196.  
  197.         unsigned __int128 z = (unsigned __int128)2 * t - (unsigned __int128)n;
  198.         q[n] = z;
  199.         FastIO::wrt(z);
  200.     }
  201.     FastIO::flu();
  202. }
  203. int main() {
  204.     ini();
  205.     slv();
  206.     return 0;
  207. }
  208.  
Success #stdin #stdout 0.23s 183652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6JUGio
language:
C++14 (clang 8.0)
created:
5 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!