TopCoder SRM 789 : Div1 Easy Div2 Hard ThreeDigits

EasyもMediumもしょうもないミスでげんなり。
https://community.topcoder.com/stat?c=problem_statement&pm=16246&rd=18188

問題

非負整数X,Y,Zが与えられる。
(X^Y)/Zについて、小数点前後の3桁を答えよ。

解法

整数部分は下3桁しか興味がないので、まずP=(X^Y) mod (Z*1000)を取ろう。
P/Zの整数部分は1000未満なのは確定するので、あとはP/Zの小数部分を加えよう。
以下2点注意。

• PはZ*1000以下だが、(X^Y)はZ*1000以上かもしれないので、その際は頭に0を補わなければならない。
  • これはX^Yを1000を超えるまで少し計算してもよいし、対数値を取って(X^Y)/Zが999を超えるか判定してもよい。
• P/Zの小数部分をsprintfで取る場合、大きめに桁を取っておいた方がよい。そうしないと丸めが発生してミスする。

ll modpow(ll a, ll n,ll mo) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class ThreeDigits {
	public:
	string calculate(int X, int Y, int Z) {
		
		ll a=modpow(X,Y,Z*1000);
		char buf[256];
		sprintf(buf,"%.12lf",(a%Z)*1.0/Z);
		string S=to_string(a/Z)+(buf+1);
		
		if(exp(log(X)*Y-log(Z))>999) S="00000"+S;
		
		int i,j;
		string T;
		FOR(i,S.size()) {
			if(S[i]=='.') {
				for(j=max(0,i-3);j<=i+3;j++) T+=S[j];
				return T;
			}
		}
		return "";
	}
}

まとめ

なんだかなｌ。