菜单

POJ刷题计划 POJ-1001

8月 8, 2018 - 算法
POJ刷题计划 POJ-1001

前言

准备开一个无限深坑,按序号往后做POJ的题目,尽量记录下来一些想法吧。鶸的挣扎系列了解一下(x

POJ-1001

题目描述

Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.
This problem requires that you write a program to compute the exact value of R n where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.

Input

The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.

Output

The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don’t print the decimal point if the result is an integer.

Sample Input

95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12

Sample Output

548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201

题目大意

其实题意很好理解,就是求R^n,要求高精度。

题目分析

所谓大数的乘方,其实就是大数乘法的叠加,相信大家也有各自的大数加减乘的模板,我这里用的是最近刚刚弄好的利用卷积和FFT的大数乘法模板,但从运算角度会比直接利用数组快一些。
思路也很简单,读取的时候记录小数点的位置,利用乘法的模板计算完毕后,再算出小数点应在的位置,之后再社区小数点后数字里不必要的0
比如1.00^3,读入字符串形式的1.00,在从后往前将其转化为int类型后放在数组里,读入数组的为001形式,从后往前数记录小数点前的字符数为2,于是我们可以知道最后结果中保留小数点应该从后往前放在第2*3=6个数字之前,数组中经过模板计算出的结果应该是0000001,再去掉不必要的前导6个0,最后只输出1.

注意

这个题看起来没什么玄机,但是测试数据非常恐怖,在这里举出几个典型的例子

000.10 1
000000 1
000.00 1
.00000 0
000010 1

这就要求我们在输入的时候处理数据,在输出的时候再处理数据,并且要把这些情况考虑进去,这道题我wa了一个上午才过去QAQ。

代码实现

后记

这个题真的是超级坑啊,数据可以说是极其严格了,一个不注意就是wa,希望来者多多注意吧233333333.

标签:, , ,

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注