例题 Problem link XDOJ1029

最高位

x=nmx=10lg⁡nm(alog⁡ab=b)x=10mlg⁡nx = n^m \\ x = 10^{\lg n^m} \hspace{4em} (a^{\log _a b} = b) \\ x = 10^{m\lg n}

问题变成求10mlg⁡n10^{m\lg n}的最高位和最低位，为什么用10为底，因为是10进制。

在10的指数函数中，f(x)=10xf(x) = 10^x，函数值的最高位从1~9取决于x的小数部分，并且不管10的多少次幂后，最高位都是和小数部分相关且一致，所以只需要求10的小数部分次幂即可

设k为mlg⁡n的小数部分k=mlg⁡n−⌊mlg⁡n⌋highest digit=⌊10k⌋设k为m\lg n 的小数部分 \\ k = m \lg n - \lfloor m \lg n \rfloor \\ highest\ digit = \lfloor 10^k \rfloor 

1
2
3
4
5
6
int highest_digit(double n, double m)
{
	double x = m * log10(n);
	double k = x - (int)x;
	return (int)(pow(10, k) + 0.000001);
}

最低位

  1. 最低位是循环的，可以存下来直接查表
  2. 直接求快速幂模10也不是不行

sample code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<stdlib.h>
#include<cmath>
using namespace std;
int main(void)
{
	int T;
	cin >> T;
	int b[4] = {2, 4, 8, 6};
	int n, t1, max, min;
	double x, k;
	while(T--)
	{
		cin >> n;
		t1 = (n - 1) % 4;
		x = n * log10(2.0);
		k = x - (int)x;
		max = (int)(pow(10, k) + 0.000001);
		min = b[t1];
		cout << max << " " << min << endl;
	}
	return 0;
}