yukicoder No.376 立方体のN等分 (2)

※他の方の解説とは違い、因数分解を用いない回答です

基本的な考え方はyukicoder No.375 立方体のN等分 (1) - メモに同じ
ただし、制約が大きいのであんな愚直な全探索では通らない
約数を求めてその組み合わせを試して～～としても良いが、先に思いついたのがこの解法だったのでそれを解説

min{a+b+c-3|N=abc}を求める問題だった。a,b,cをNの約数でa≦b≦cとする。このとき $a\leq\sqrt[3]{N}$ となる。
aをそのようなものから適当に固定した時のa+b+cの最小値は、もちろんa+min{b+c|bc=N/a}で与えられ、「正の数Kについてmin{A+B|AB=K}は|A-B|が最小となるようなとき達成される（※）」ことから、bは√(N/a)以下のN/aの約数で最大のものを取れば良い
（※(A+B)^2=(A-B)^2+4ABでありABは定数なので、A+Bを小さくすることは|A-B|を小さくすることに同じ）
ということで次のように書ける

int main(){
	long n,a,b,s,t;
	scanf("%ld",&n);
	s=n;
	for(a=cbrt(n)+1;a>0;a--){
		if(n%a!=0)continue;
		b=sqrt(n/a);
		while(n/a%b!=0)b--;
		//n/aの約数で、平方根に一番近いものを探す
		t=a+b+n/a/b-3;
		if(t<s)s=t;
	}
	printf("%ld %ld",s,n-1);
	return 0;
}

このコードで一番時間がかかるのは恐らく
99999999504720=45360*2204585527
が入力として与えられた時。（45360は10^(14/3)以下の最大の高度合成数で、2204585527は(10^14)/45360以下の最大の素数）
この時にも1.5秒程度で通ることが確認できたので、テストケースが追加されてもTLEになることは多分ないでしょう。
約数が絡んでくるので正確なオーダーはよくわからないけれど。

縮められるところをちゃちゃっと縮めて

long n,s,i=5e4,j;
main(){
	scanf("%ld",&n);
	for(s=n;--i;s=n%i|(j=i+j+n/i/j-3)>s?s:j)for(j=sqrt(n/i)+2;n%i<1&&n/i%--j;);
	s=!printf("%ld %ld",s,n-1);
}

n/iが0になる可能性があるのでjの初期値に気をつける必要がある
143B

16/06/17追記
ところで内側のループをぐっと睨むと、2つの条件式はまとめられることに気付く

long n,s,i=5e4,j;
main(){
	scanf("%ld",&n);
	for(s=n;--i;s=n%i|(j=i+j+n/i/j-3)>s?s:j)for(j=sqrt(n/i)+2;n%i<n/i%--j;);
	s=!printf("%ld %ld",s,n-1);
}

また、それとは別件で

s=n%i|(j=i+j+n/i/j-3)>s?s:j
s=n%i?s:fmin(i+j+n/i/j-3,s)

と書き換える事ができる。これ自体は同じ長さだが、これによりjがlongである必要がなくなったので、mainの引数にすることができるようになった

long n,s,i=5e4;
main(j){
	scanf("%ld",&n);
	for(s=n;--i;s=n%i?s:fmin(i+j+n/i/j-3,s))for(j=sqrt(n/i)+2;n%i<n/i%--j;);
	s=!printf("%ld %ld",s,n-1);
}

139B