結果

問題 No.376 立方体のN等分 (2)
コンテスト
ユーザー kurenai3110
提出日時 2016-12-20 16:42:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,154 bytes
コンパイル時間 822 ms
コンパイル使用メモリ 80,404 KB
実行使用メモリ 10,148 KB
最終ジャッジ日時 2024-12-14 11:24:13
合計ジャッジ時間 68,683 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 WA * 24 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

pair<long long,long long> solve(long long n){
	long long tmin=n-1;
	vector<pair<int,int>>X;
	X.push_back(make_pair(1,n));
	
	vector<pair<long long,int>>div;
	for(int i=2;i*i<=n;i++){
		int cnt=0;
		while(!(n%i)){
			n/=i;
			cnt++;
		}
		if(cnt)	div.push_back(make_pair(i,cnt));
	}
	if(n!=1)div.push_back(make_pair(n,1));

	for(int i=0;i<div.size();i++){
		int Xsize=X.size();
		for(int j=0;j<Xsize;j++){
			for(int k=0;k<div[i].second;k++){
				X.push_back(make_pair(X[j].first*pow(div[i].first,k+1),X[j].second/pow(div[i].first,k+1)));
			}
		}
	}
	
	int ti=0;
	for(int i=0;i<X.size();i++){
		if(tmin > X[i].first+X[i].second-2){
			tmin = X[i].first+X[i].second-2;
			ti=i;
		}
	}

	return X[ti];	
}

int main() {
	long long n;cin>>n;
	long long tmax=n-1;

	pair<long long,long long>d1 = solve(n);
	pair<long long,long long>d2 = solve(d1.first);	
	pair<long long,long long>d3 = solve(d1.second);

	long long tmin = min(d1.first + d3.first + d3.second -3,d1.second + d2.first + d2.second -3);
	
	cout<<tmin<<" "<<tmax<<endl;
	
	return 0;
}
0