This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// 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; }