問題 113 Power of Cryptography

正の整数同士のべき乗 p = kn において、教えてくれた n, p の値に対し、式を満たす k を求める問題。

各データの範囲:
   1 <= n <= 200
   1 <= p < 10101
   1 <= k <= 109

対数計算すればすぐに判ることだが、k は 230 以下なので、32ビットの unsigned long 整数でOK。

p について、桁数の多い値を正確にプログラムに取り込むのは困難なので、仮数部 x と指数部 y に以下のように分けて記録する。浮動小数点になり、精度は落ちるかもしれないが、101桁の巨大整数にも対応できる。

    p = x * 10y  ただし、 0.1 <= x < 1

それで、y は10進数の桁数になる。例えば、Sample Input にある数字 4357186184021382204544 を  0.4357186184021382 * 1022 と表現するし、4 を 0.4 * 101 とする。

仮数部 x は、pの入力行の先頭に 「0.」(つまり小数点)をつけ、sscanf 関数に読み込ませば、x の値が得られる。指数部 y は入力の桁数から正確に読み取れる。

(あくまでも参考程度)
char buf[120];
double x;
int y;
buf[0] = '0', buf[1] = '.'; scanf("filename=113-power-of-cryptography.html, line=25, k=1 \n", buf+2); for (y = 0; isdigit(buf[y+2]); y++); sscanf(buf, "0.000000", &x);

それで、

   p = kn
   log10p = n * log10k
   log10(x * 10y) = n * log10k
   y + log10x = n * log10k
   k = 10(y + log10x)/n

となる。k を pow 関数 pow(10, (y + log10x) / n) で計算できる。

ちなみに、Gnu C の仮数部精度は、float で 7桁、double で16桁、long double で 20桁となっているようだ。たとえ、16桁で計算してみると、

   p = 0.4357186184021382 * 1022 → x = 0.4357186184021382、 y = 22
   n = 7
   k = 10(y + log10x)/n = 10(22 + log100.4357186184021382)/7
     = 10(22 - 0.3607938821194398)/7 = 103.091315159697222
     = 1233.9999999999975

正解は 1234 なので、誤差にどう対処するかは課題。

例えば、k-1, k, k+1 等と、得られた k の近辺の値で確かめ算して、誤差の一番少ないものを答えとするとか。

Comments are closed.

Post Navigation