アルゴリズム忘備録

競技プログラミングとかデータ分析とか

TopCoder SRM789 Div1 ThreeDigits

community.topcoder.com

 

int32の範囲の X, Y, Zが与えられる。 X^Y/Z の商の下位3桁及び小数点以下の上位3桁を求めよ。

 

問題では0埋めするとかしないとか余計な考察がついてるので若干あれだが、問題の本質はこんな感じ。小数点以下の上位三桁は P=X^Y \bmod ZなるPを計算してやり、1000P / Zを切り捨てればよい。問題は商の下位3桁だが、これは X^Y \bmod 1000Zを計算すると良い。kmjp氏のブログ を参考にした。

TopCoder SRM 789: Div1 Easy Div2 Hard ThreeDigits - kmjp's blog

 

なぜかというと、 Q * 1000Z + P' = X^Y - Pと表したとき、Q*1000 + P'/Z = (X^Y-P)/Zとなり、ここで P' < 1000Zなので、 P'/Z < 1000 かつ Q*1000 \bmod 1000 = 0であるから、P/Z(X^Y-P)/Zの下位3桁となっているのである。Pの定義よりこれは整数となるため、これが答え。