解决求大数位数与前m位数后m位数问题

佚名 6年前 (2019-04-16) 随笔 1978人围观抢沙发百度已收录

一.问题介绍：求大数位数
问：给出一个n,请求出n的阶乘是几位数？
思考：首先我们需要知道一个概念，对一个数n取以10为底作对数可以知道它的位数（比如：1000,log10(1000）=3)
转化成数学式子：10^（t-1）<= n <10^t t就是位数 位数t=log（10）n

问题举例：HDU 1018 Big Number
问题思路：求一个数的阶乘的位数，因为乘出来的数很大，所以不能用一般的方法去解决 
这里要求的是 1*2*3*4*5*6*……*n 的位数，同理把 n 换成1*2*3*4*5*6*……*n ,整理一下得到：(int)log10(1*2*3*4*5*6……*n)+1 = (int)(log10(1) +log10(2)+……log10(n) )+1 ,
注意：使用log函数时需要保证double ans=log10(double t),使用时需要注意一下，log里面的指数是double类型的

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cmath>
 4 using namespace std;
 5 long long n;
 6 int solve(long long m)
 7 {
 8     double ans=0;
 9     for(double i=1;i<=m;i++)
10     {
11     ans+=(double)log10(i);
12    }
13     ans=(int)ans+1;
14     return ans;
15 }
16 int main()
17 {
18     cin>>n;
19     while(n--)
20     {
21         long long m;
22         cin>>m;
23         cout<<solve(m)<<endl;
24     }
25 }

View Code

二.问题介绍：求前m位数与后m位数

(2)K 次方 求一个数 n 的k 次方的前3 位后三位。 求后三位好求，快速幂取模，注意补零的情况。 求前三位：我们可以求出n^k的位数 m = (int)(k*log10(n)) + 1 ,这样前三位 h = n^k / 10^(m - 3),因为求的是前三位so 100 <= h <= 999 ,可以遍历得到，但是怎样遍历呢？可以同时取log然后函数就变成递增的，然后h从最小的100开始枚举就可以了。