結果
問題 |
No.375 立方体のN等分 (1)
|
ユーザー |
![]() |
提出日時 | 2016-06-07 16:06:06 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 281 ms / 5,000 ms |
コード長 | 1,521 bytes |
コンパイル時間 | 1,282 ms |
コンパイル使用メモリ | 96,888 KB |
実行使用メモリ | 74,496 KB |
最終ジャッジ日時 | 2024-10-11 21:05:26 |
合計ジャッジ時間 | 3,162 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include<iostream> #include<cmath> #include<algorithm> #include<map> using namespace std; #define MAX 316228 long long N; bool arr[MAX+1]; long long insuu[MAX]; long long insuun=0; long long pn[MAX]; long long pc=0; long long ansmin; map<long long,map<long long,map<long long,map<long long,long long>>>> memo; void search2(long long a,long long b,long long c,int sn,int pl){ if(memo.find(a)!=memo.end()&&memo[a].find(b)!=memo[a].end()&&memo[a][b].find(c)!=memo[a][b].end()&&memo[a][b][c].find(sn)!=memo[a][b][c].end()){ return; } else{ memo[a][b][c][sn]=a+b+c; memo[a][c][b][sn]=a+b+c; memo[b][a][c][sn]=a+b+c; memo[b][c][a][sn]=a+b+c; memo[c][b][a][sn]=a+b+c; memo[c][a][b][sn]=a+b+c; } if(a+b+c>=ansmin) return; if(sn==-1||sn==insuun){ ansmin=min(ansmin,a+b+c); return; } search2(a*insuu[sn],b,c,sn+pl,pl); search2(a,b*insuu[sn],c,sn+pl,pl); search2(a,b,c*insuu[sn],sn+pl,pl); } int main(){ cin>>N; long long ansmax=N-1; for(long long i=0;i<=MAX;i++){ arr[i]=true; } arr[0]=false; arr[1]=false; for(long long i=2;i<=MAX;i++){ if(arr[i]){ pn[pc]=i; pc++; for(long long j=i*2;j<=MAX;j+=i){ arr[j]=false; } } } for(long long i=0;i<pc;i++) insuu[i]=0; for(long long i=0;i<pc;i++){ while(N%pn[i]==0){ N/=pn[i]; insuu[insuun]=pn[i]; insuun++; } if(N==1) break; } if(N!=1) insuu[insuun]=N,insuun++; ansmin=ansmax+3; search2(1,1,1,insuun-1,-1); ansmin-=3; cout<<ansmin<<" "<<ansmax<<endl; }