fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int a,b,c;
  9.     if(!(cin>>a>>b>>c)) return 0;
  10.  
  11.     int mx = max(a, max(b,c));
  12.     vector<int> isP(mx+1,1), primes;
  13.     isP.assign(mx+1,1); isP[0]=isP[1]=0;
  14.     for(int i=2;i*i<=mx;i++) if(isP[i]) for(long long j=1LL*i*i;j<=mx;j+=i) isP[j]=0;
  15.     for(int i=2;i<=mx;i++) if(isP[i]) primes.push_back(i);
  16.     reverse(primes.begin(), primes.end());
  17.  
  18.     const uint32_t MOD = 1u<<30, MASK = MOD-1;
  19.  
  20.     vector<vector<int>> pw(primes.size());
  21.     for (size_t i=0;i<primes.size();++i){
  22.         int p=primes[i]; long long cur=1;
  23.         while(cur<=mx){ pw[i].push_back((int)cur); if(cur>mx/p) break; cur*=p; }
  24.     }
  25.  
  26.     vector<int> vx = {a}, vy = {b}, vz = {c};
  27.     vector<uint32_t> dp(1,1), ndp;
  28.  
  29.     for (size_t i=0;i<primes.size();++i){
  30.         vector<int> nx, ny, nz;
  31.         nx.reserve(vx.size()*3); ny.reserve(vy.size()*3); nz.reserve(vz.size()*3);
  32.         for (int x: vx) for (int t: pw[i]) { if(t>x) break; nx.push_back(x/t); }
  33.         for (int y: vy) for (int t: pw[i]) { if(t>y) break; ny.push_back(y/t); }
  34.         for (int z: vz) for (int t: pw[i]) { if(t>z) break; nz.push_back(z/t); }
  35.         sort(nx.begin(), nx.end()); nx.erase(unique(nx.begin(), nx.end()), nx.end());
  36.         sort(ny.begin(), ny.end()); ny.erase(unique(ny.begin(), ny.end()), ny.end());
  37.         sort(nz.begin(), nz.end()); nz.erase(unique(nz.begin(), nz.end()), nz.end());
  38.  
  39.         vector<int> idxX(mx+1,-1), idxY(mx+1,-1), idxZ(mx+1,-1);
  40.         for (int j=0;j<(int)nx.size();++j) idxX[nx[j]] = j;
  41.         for (int j=0;j<(int)ny.size();++j) idxY[ny[j]] = j;
  42.         for (int j=0;j<(int)nz.size();++j) idxZ[nz[j]] = j;
  43.  
  44.         int X=vx.size(), Y=vy.size(), Z=vz.size();
  45.         int NX=nx.size(), NY=ny.size(), NZ=nz.size();
  46.         ndp.assign((size_t)NX*NY*NZ, 0);
  47.  
  48.         vector<vector<pair<int,int>>> TX(X), TY(Y), TZ(Z);
  49.         for(int px=0;px<X;++px){
  50.             int x=vx[px];
  51.             for(int e=0;e<(int)pw[i].size();++e){ int t=pw[i][e]; if(t>x) break; TX[px].push_back({idxX[x/t], e}); }
  52.         }
  53.         for(int py=0;py<Y;++py){
  54.             int y=vy[py];
  55.             for(int e=0;e<(int)pw[i].size();++e){ int t=pw[i][e]; if(t>y) break; TY[py].push_back({idxY[y/t], e}); }
  56.         }
  57.         for(int pz=0;pz<Z;++pz){
  58.             int z=vz[pz];
  59.             for(int e=0;e<(int)pw[i].size();++e){ int t=pw[i][e]; if(t>z) break; TZ[pz].push_back({idxZ[z/t], e}); }
  60.         }
  61.  
  62.         size_t strideYZ = (size_t)Y*Z, strideNZ = (size_t)NY*NZ;
  63.         for(int px=0;px<X;++px){
  64.             for(int py=0;py<Y;++py){
  65.                 size_t base = (size_t)px*strideYZ + (size_t)py*Z;
  66.                 auto &VX = TX[px]; auto &VY = TY[py];
  67.                 for(int pz=0;pz<Z;++pz){
  68.                     uint32_t val = dp[base + pz];
  69.                     if(!val) continue;
  70.                     auto &VZ = TZ[pz];
  71.                     for (auto [ix, ex]: VX){
  72.                         size_t baseX = (size_t)ix*strideNZ;
  73.                         for (auto [iy, ey]: VY){
  74.                             size_t baseY = baseX + (size_t)iy*NZ;
  75.                             for (auto [iz, ez]: VZ){
  76.                                 uint32_t add = (uint32_t)(((uint64_t)val * (ex + ey + ez + 1)) & MASK);
  77.                                 uint32_t &cell = ndp[baseY + iz];
  78.                                 cell += add; cell &= MASK;
  79.                             }
  80.                         }
  81.                     }
  82.                 }
  83.             }
  84.         }
  85.  
  86.         dp.swap(ndp);
  87.         vx.swap(nx); vy.swap(ny); vz.swap(nz);
  88.     }
  89.  
  90.     uint32_t ans = 0;
  91.     for (uint32_t v: dp){ ans += v; ans &= MASK; }
  92.     cout << ans << '\n';
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2 2 2
stdout
copy 
20
https://ideone.com/sGVp3m
language:
C++14 (gcc 8.3)
created:
9 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!