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.     int a,b,c;
  8.     if(!(cin>>a>>b>>c)) return 0;
  9.     int N = max({a,b,c});
  10.     vector<int> primes;
  11.     vector<bool> is(N+1,true);
  12.     is[0]=is[1]=false;
  13.     for(int i=2;i*i<=N;i++) if(is[i]) for(long long j=1LL*i*i;j<=N;j+=i) is[(int)j]=false;
  14.     for(int i=2;i<=N;i++) if(is[i]) primes.push_back(i);
  15.     sort(primes.rbegin(), primes.rend());
  16.     vector<vector<int>> pw;
  17.     pw.reserve(primes.size());
  18.     for(int p:primes){
  19.         vector<int> v(1,1);
  20.         long long x=1;
  21.         while(x<=N/p){
  22.             x*=p;
  23.             v.push_back((int)x);
  24.         }
  25.         pw.push_back(move(v));
  26.     }
  27.     const uint32_t MASK = (1u<<30)-1u;
  28.     auto pack = [](int x,int y,int z)->uint64_t{
  29.         return (uint64_t)x<<28 | (uint64_t)y<<14 | (uint64_t)z;
  30.     };
  31.     unordered_map<uint64_t,uint32_t> cur, nxt;
  32.     cur.reserve(1024);
  33.     cur[pack(a,b,c)] = 1u;
  34.     for(size_t idx=0; idx<primes.size(); ++idx){
  35.         const vector<int>& pws = pw[idx];
  36.         nxt.clear();
  37.         nxt.reserve(cur.size()*2+1024);
  38.         for(auto &it: cur){
  39.             uint64_t key=it.first;
  40.             uint32_t val=it.second;
  41.             int x = (int)(key>>28);
  42.             int y = (int)((key>>14)&((1<<14)-1));
  43.             int z = (int)(key & ((1<<14)-1));
  44.             int ex_max = upper_bound(pws.begin(), pws.end(), x) - pws.begin() - 1;
  45.             int ey_max = upper_bound(pws.begin(), pws.end(), y) - pws.begin() - 1;
  46.             int ez_max = upper_bound(pws.begin(), pws.end(), z) - pws.begin() - 1;
  47.             for(int ex=0; ex<=ex_max; ++ex){
  48.                 int nx = x / pws[ex];
  49.                 for(int ey=0; ey<=ey_max; ++ey){
  50.                     int ny = y / pws[ey];
  51.                     for(int ez=0; ez<=ez_max; ++ez){
  52.                         int nz = z / pws[ez];
  53.                         uint64_t k2 = pack(nx,ny,nz);
  54.                         uint32_t add = (uint32_t)(((uint64_t)val * (uint32_t)(ex+ey+ez+1)) & MASK);
  55.                         auto it2 = nxt.find(k2);
  56.                         if(it2==nxt.end()) nxt.emplace(k2, add);
  57.                         else { it2->second += add; it2->second &= MASK; }
  58.                     }
  59.                 }
  60.             }
  61.         }
  62.         cur.swap(nxt);
  63.     }
  64.     uint32_t ans = 0;
  65.     for(auto &it: cur){ ans += it.second; ans &= MASK; }
  66.     cout << ans << '\n';
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
1 2 3
stdout
copy 
14
https://ideone.com/ahjzJs
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!