Advertisement
Guest User

isduck

a guest
Jan 25th, 2020
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. vector < int > prime;
  7. vector < pair < int, int > > factor;
  8. int comp[1000010];
  9. int v;
  10.  
  11.  
  12. void crivo(){
  13.     comp[1] = 1;
  14.  
  15.     for(int i=2; i<=v; i++){
  16.         if(comp[i] == 0){
  17.             prime.push_back(i);
  18.             for(int j=2*i; j<=v; j*=i){
  19.                 comp[j] = 1;
  20.             }
  21.         }
  22.     }
  23. }
  24.  
  25. int solve(vector < int > used, int f, int aux, int d1, int d2){
  26.     if(aux == 0 && f == factor.size()) return solve(used, 0, 1, d1, d2);
  27.    
  28.     if(aux == 1 && f == factor.size()){
  29.         int d3 = v / (d1 * d2);
  30.  
  31.         return 2*d1*d2 + 2*d1*d3 + 2*d2*d3;
  32.     }
  33.  
  34.     int resp = 0x7f7f7f7f;
  35.  
  36.     resp = min(resp, solve(used, f+1, aux, d1, d2));
  37.    
  38.     for(int i=used[f]; i<factor[f].second; i++){
  39.         used[f]++;
  40.         resp = min(resp, (aux == 1 ? solve(used, f+1, aux, d1*factor[f].first, d2) : solve(used, f+1, aux, d1, d2*factor[f].first)));
  41.     }
  42.  
  43.     return resp;
  44. }
  45.  
  46. int main(){
  47.     cin >> v;
  48.  
  49.     crivo();
  50.  
  51.     int k = v;
  52.     int aux = 0;
  53.     factor.push_back(make_pair(1, 0));
  54.     while(k > 1){
  55.         if(k % prime[aux] == 0){
  56.             factor[factor.size()-1].first = prime[aux];
  57.             factor[factor.size()-1].second++;            
  58.             k = k / prime[aux];
  59.         }else{
  60.             aux++;
  61.             if(factor[factor.size()-1] != make_pair(1, 0)) factor.push_back(make_pair(1, 0));
  62.         }
  63.     }
  64.  
  65.     /*
  66.     for(int i=0; i<factor.size(); i++){
  67.         cout << factor[i].first << " " << factor[i].second << "\n";
  68.     }
  69.     */
  70.    
  71.     vector < int > u(factor.size(), 0);
  72.  
  73.     cout << solve(u, 0, 0, 1, 1) << "\n";
  74.  
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement