問題はこちら
No.376 立方体のN等分 (2) - yukicoder
※他の方の解説とは違い、因数分解を用いない回答です
基本的な考え方はyukicoder No.375 立方体のN等分 (1) - メモに同じ
ただし、制約が大きいのであんな愚直な全探索では通らない
約数を求めてその組み合わせを試して~~としても良いが、先に思いついたのがこの解法だったのでそれを解説
min{a+b+c-3|N=abc}を求める問題だった。a,b,cをNの約数でa≦b≦cとする。このときとなる。
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