結果
問題 |
No.376 立方体のN等分 (2)
|
ユーザー |
![]() |
提出日時 | 2019-02-15 12:20:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 227 ms / 5,000 ms |
コード長 | 1,115 bytes |
コンパイル時間 | 2,375 ms |
コンパイル使用メモリ | 205,984 KB |
最終ジャッジ日時 | 2025-01-06 21:09:45 |
ジャッジサーバーID (参考情報) |
judge1 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; 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;} template<typename T> map<T, Int> factorize(T x){ map<T, Int> res; for(Int i=2;i*i<=x;i++){ while(x%i==0){ x/=i; res[i]++; } } if(x!=1) res[x]++; return res; } //INSERT ABOVE HERE signed main(){ Int n; cin>>n; auto m=factorize(n); using P = pair<Int, Int>; vector<P> v; for(auto p:m) v.emplace_back(p); Int mi=n,ma=0; function<void(Int, Int, Int, Int)> dfs= [&](Int a,Int x,Int y,Int z){ if(a==(Int)v.size()){ chmin(mi,x-1+y-1+z-1); chmax(ma,x-1+y-1+z-1); return; } Int s=v[a].first,t=v[a].second; vector<Int> po(t+1,1); for(Int i=0;i<t;i++) po[i+1]=po[i]*s; for(Int i=0;i<=t;i++){ for(Int j=0;i+j<=t;j++){ Int k=t-(i+j); dfs(a+1,x*po[i],y*po[j],z*po[k]); } } }; dfs(0,1,1,1); cout<<mi<<" "<<ma<<endl; return 0; }