Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector < int > prime;
- vector < pair < int, int > > factor;
- int comp[1000010];
- int v;
- void crivo(){
- comp[1] = 1;
- for(int i=2; i<=v; i++){
- if(comp[i] == 0){
- prime.push_back(i);
- for(int j=2*i; j<=v; j*=i){
- comp[j] = 1;
- }
- }
- }
- }
- int solve(vector < int > used, int f, int aux, int d1, int d2){
- if(aux == 0 && f == factor.size()) return solve(used, 0, 1, d1, d2);
- if(aux == 1 && f == factor.size()){
- int d3 = v / (d1 * d2);
- return 2*d1*d2 + 2*d1*d3 + 2*d2*d3;
- }
- int resp = 0x7f7f7f7f;
- resp = min(resp, solve(used, f+1, aux, d1, d2));
- for(int i=used[f]; i<factor[f].second; i++){
- used[f]++;
- 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)));
- }
- return resp;
- }
- int main(){
- cin >> v;
- crivo();
- int k = v;
- int aux = 0;
- factor.push_back(make_pair(1, 0));
- while(k > 1){
- if(k % prime[aux] == 0){
- factor[factor.size()-1].first = prime[aux];
- factor[factor.size()-1].second++;
- k = k / prime[aux];
- }else{
- aux++;
- if(factor[factor.size()-1] != make_pair(1, 0)) factor.push_back(make_pair(1, 0));
- }
- }
- /*
- for(int i=0; i<factor.size(); i++){
- cout << factor[i].first << " " << factor[i].second << "\n";
- }
- */
- vector < int > u(factor.size(), 0);
- cout << solve(u, 0, 0, 1, 1) << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement