蓝桥杯 ADV-206 不大的数

蓝桥杯 ADV-206 不大的数"/>

蓝桥杯 ADV-206 不大的数

蓝桥杯 ADV-206 不大的数

问题描述
在当今的大数据时代，超大数的高精度计算已经成为众多领域的热门研究之一。现在T校也想在此领域有所造诣已造福于全社会，然而由于时间有限，所以短时间内难以找出大数计算的通用算法，于是学校找到了同学中的“神霸”——你来帮忙，并仅要求你能在数并不算大的时候给出结果。又出于某种特殊需要，也并不要求你给出数的全部结果，而只是要求结果的前10位（注意不是后10位），并考虑到2的幂次的特殊性和典型性，所以要你计算的数均为2的幂次。

输入格式
一个自然数n。

输出格式
2的n次幂的前10位。

样例1 输入
60

样例1 输出
1152921504

样例2 输入
60000

样例2 输出
6305794870

数据规模和约定
0<=n<=10000000

思路解析

题目中只要求前十位数，目的也就是让我们避免存储的数字过大。我们可以将大数转化为小数，再以10倍的 速率不断增大，最多达到十位十进制，从而获取到该数或者该数的前十位。
将较大的数化为小数有一个技巧：
我们知道， 2 n = 1 0 l g 2 n = 1 0 n ∗ l g 2 2^n=10^{lg2^n}=10^{n*lg2} 2n=10lg2n=10n∗lg2
其十进制位数为 [ l g 2 n ] = n ∗ [ l g 2 ] [lg2^n]=n*[lg2] [lg2n]=n∗[lg2]
所以可通过公式 1 0 n ∗ l g 2 − n ∗ [ l g 2 ] 10^{n*lg2 - n*[lg2]} 10n∗lg2−n∗[lg2]将 2 n 2^n 2n化为一位整数的小数形式。
所以有，

#include<iostream>
#include<cmath>
using namespace std;long long int MAX = 1000000000;int main() {double n;double d;cin >> n;d = log2(MAX);if (n <= d) {printf("%d", pow(2.0, n));return 0;}double res = n*log10(2) - (long long)(n*log10(2));res = pow(10.0, res);while (res < MAX) res *= 10;printf("%lld", (long long)res);return 0;
}