SRM335 Div2 500

とぷこだ 過去問

問題

nのk-multifactorialをfac_k(n)とし、(n-χ*k)が0より大きいものの積と定義する。
例えば、14の3-multifactorialは14*11*8*5*2=12320となる。
より正確に書くと、

  • fac_k(n) = n if k>=n
  • fac_k(n) = n*fac_k(n-k) if k

nとkが与えられるので、fac_k(n)を表す文字列を返す(leading-zeroはなし)。
もし、10^18を超えるならばoverflowという文字列を返す。

考え方

やるだけ。fac_1(20)=20!でオーバーフローするので、高々20回程度しか掛け算しない(はず)。
オーバーフローの判定は、doubleを使って10^18を超えるかどうか判定し、するならoverflow、しないならlong longで計算するようにする。

反省

前に知ってたけど、オーバーフローが怪しい場合はdoubleで計算してオーバーフローチェックするといい。