kmjp's blog

競技プログラミング参加記です

yukicoder : No.219 巨大数の概算

ぐぬぬ。
http://yukicoder.me/problems/593

問題

整数A,Bが与えられる。
 A^BX.Y * 10^Zと指数表記の形で表現したい。

X,Y,Zを求めよ。
(なお、本番後にX.Yは0.1まで誤差が許容されることとなった。)

解法

 P = (log_{10} A)*Bを計算する。
Pの整数部分はZとなり、残りの部分(P-Z)について 10^{P-Z}を求めるとそれがX.Yとなる。

当初は誤差が許容されなかったため、long doubleですら誤差死したが、許容後はdoubleで普通に通るようになった。

void solve() {
	int N;
	ll A,B;
	
	cin>>N;
	while(N--) {
		cin>>A>>B;
		
		long double la=log10((long double)A)*B;
		ll t=floor(la)+0.1;
		int x=floor(pow(10,(la-t)+2+(1e-9)))+0.0000001;
		_P("%d %d %lld\n",x/100,x/10%10,t);
	}
}

まとめ

こういう誤差死はどう気を付ければいいんだろうな。
とりあえずlong doubleにしておけば少しは安全?