首页 > 代码库 > a^b的前n位数
a^b的前n位数
假设我们现在需要知道 ab 的后 n 位数或前 n 位数，简单直观的做法就是求出 ab 的值，然后在分别取前 n位或后 n位，不过在 a，b很大的情况下显然是无法存储的。所以，直接求是不可能的了。
让我们先来看看后 n 位如何求？因为我们只要后 n 位，那么我们都知道把 ab 的值模上一个10n 就是所求。根据求模的性质：ab % n = (a%n)b % n;然后用快速幂跑一遍即可。
1 int QuickPow (__int64 a, __int64 b) 2 { 3 __int64 r = 1; 4 while (b) 5 { 6 if (b&1) 7 r = (r*a) % (__int64)pow(10.0, n*1.0); 8 a = ( a*a) % (__int64)pow(10.0, n*1.0); 9 b >>= 1;10 }11 return r;12 }
关键是前 n 如何求？我们假设 ab = c。再设 log10 (c) = d。另 Int 为 d 的整数部分，k 为小数部分，那么 10Int = 100......0(共Int个0)，不难发现，除了第一位是1外其余均为0，也就说，10k 最终将直接影响最左边的 N 位数。将这个结果乘以1，就是前1位的答案，乘以10，就是前2位的答案。。。类推！
后来发现任何一个数字 n 都可以表示成10(a+b) 。其中 a整数，b为小数。例如
n=87455时，a=4,b=0.941784644.
有规律.10a =10000.10b =8.7455.
所以n的左边数起第一位数字。就是10b 的第一位有效数字，第二数字，是10^b的第二位有效数字。。。。以次类推
以hdu 1060为例：
#include <cstdio>#include <cstring>#include <cmath>using namespace std;int main(){ int t; __int64 n; __int64 Int; double a, d; scanf("%d", &t); while(t--) { scanf("%I64d", &n); a = n*log10(n*1.0); Int = (__int64)a; d = a - Int; printf("%I64d\n", (__int64)pow(10, d)); } return 0;}
a^b的前n位数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。