test/aoj/1642.test.cpp

• View this file on GitHub
• Last update: 2020-11-19 17:00:02+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1642

Depends on

• math/enumerate_primes.cpp
• tools/chminmax.cpp
• tools/fixpoint.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1642

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../tools/fixpoint.cpp"
#include "../../tools/chminmax.cpp"
#include "../../math/enumerate_primes.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  using ll = long long;

  auto ps=enumerate_primes(4e7);

  ll n;
  while(cin>>n,n){
    vector<ll> qs,vs;
    {
      ll t=n;
      for(auto p:ps){
        if(t<p) break;
        if(t%p) continue;
        qs.emplace_back(p);
        vs.emplace_back(0);
        while(t%p==0) t/=p,vs.back()++;
      }
      if(t!=1){
        qs.emplace_back(t);
        vs.emplace_back(1);
      }
      reverse(qs.begin(),qs.end());
      reverse(vs.begin(),vs.end());
    }

    int m=qs.size();
    ll ans=n+2;
    MFP([&](auto dfs,int t,ll x,ll y,ll z)->void{
      if(x+y+z>=ans) return;
      if(t==m){
        assert(x*y*z==n);
        chmin(ans,x+y+z);
        return;
      }
      int s=vs[t];
      vector<ll> po(s+1,1);
      for(int i=0;i<s;i++) po[i+1]=po[i]*qs[t];
      for(int i=0;i<=s;i++)
        for(int j=0;i+j<=s;j++)
          dfs(t+1,x*po[i],y*po[j],z*po[s-(i+j)]);
    })(0,1,1,1);

    cout<<ans<<endl;
  }
  return 0;
}

#line 1 "test/aoj/1642.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1642

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "tools/fixpoint.cpp"

#line 3 "tools/fixpoint.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename F>
struct FixPoint : F{
  FixPoint(F&& f):F(forward<F>(f)){}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const{
    return F::operator()(*this,forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F&& f){
  return FixPoint<F>{forward<F>(f)};
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "tools/chminmax.cpp"

#line 3 "tools/chminmax.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "math/enumerate_primes.cpp"

#line 3 "math/enumerate_primes.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// O(n)
vector<int> enumerate_primes(int n){
  vector<bool> dp((n+1)/2,false);
  vector<int> ps;
  ps.reserve(n/10);
  if(2<=n) ps.emplace_back(2);
  for(int i=3;i<=n;i+=2){
    if(!dp[i/2]) ps.emplace_back(i);
    for(int j=1;i*ps[j]<=n;j++){
      dp[i*ps[j]/2]=1;
      if(i%ps[j]==0) break;
    }
  }
  return ps;
}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 10 "test/aoj/1642.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  using ll = long long;

  auto ps=enumerate_primes(4e7);

  ll n;
  while(cin>>n,n){
    vector<ll> qs,vs;
    {
      ll t=n;
      for(auto p:ps){
        if(t<p) break;
        if(t%p) continue;
        qs.emplace_back(p);
        vs.emplace_back(0);
        while(t%p==0) t/=p,vs.back()++;
      }
      if(t!=1){
        qs.emplace_back(t);
        vs.emplace_back(1);
      }
      reverse(qs.begin(),qs.end());
      reverse(vs.begin(),vs.end());
    }

    int m=qs.size();
    ll ans=n+2;
    MFP([&](auto dfs,int t,ll x,ll y,ll z)->void{
      if(x+y+z>=ans) return;
      if(t==m){
        assert(x*y*z==n);
        chmin(ans,x+y+z);
        return;
      }
      int s=vs[t];
      vector<ll> po(s+1,1);
      for(int i=0;i<s;i++) po[i+1]=po[i]*qs[t];
      for(int i=0;i<=s;i++)
        for(int j=0;i+j<=s;j++)
          dfs(t+1,x*po[i],y*po[j],z*po[s-(i+j)]);
    })(0,1,1,1);

    cout<<ans<<endl;
  }
  return 0;
}

Back to top page