当前位置:首页 > 开发 > IT生活 > 正文

LightOJ 1282 - Leading and Trailing

发表于: 2012-07-22   作者:Abrain   来源:转载   浏览:
摘要: 题意:求n^k的前三位和后三位。2<=n<2^31,1<=k<=10^7分析: 后三位。求后三位比较简单,直接二分幂对1000求余即可。 前三位。对于给出的数据来说,不可能直接求,因此可以保留一定的位数以确保精度足够。此题应保留 3+lg(k) 位。然而,对于题给 k 的最大情况,要保留 10 位,如果用64位整

题意:求n^k的前三位和后三位。2<=n<2^31,1<=k<=10^7
分析:

  • 后三位。求后三位比较简单,直接二分幂对1000求余即可。
  • 前三位。对于给出的数据来说,不可能直接求,因此可以保留一定的位数以确保精度足够。此题应保留 3+lg(k) 位。然而,对于题给 k 的最大情况,要保留 10 位,如果用64位整数来存的话,中间过程肯定会溢出。想到 double 来保存数据,看来测试数据显然是加强过了的,不会让你轻易过的。
各种WA,各种囧。神奇的是,double 保留 9 位能过,而 long long 保留 9 位 测试样例都过不了。应该是精度的问题。
对于 long long 来说,保留 9 位(也就是进行除法),就是准确的保留 9 位;而对于 double 来说,保留 9 位,相当于小数点整体向左移,并没有将其超过 9 位的部分舍去,而是在小数点右边,进行乘法的时候也就保证了精度。

LightOJ 1282 - Leading and Trailing

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号