算法
(高精度,快速幂,数学) $O(500^2 \log P)$
首先考虑如何求位数。
我们发现在 $10^k \sim 10^{k + 1}-1, (k \ge 0)$ 之间的数均有 $k + 1$ 位。因此对于任意正整数 $x$,它的位数是 $\lfloor \log_{10}x \rfloor + 1$。
而由于2的整次幂的末位数字不为0,因此 $2^P - 1$ 的位数和 $2^P$ 的位数相同,所以 $2^P - 1$ 的位数是 $\lfloor \log_{10}{2^P} \rfloor + 1 = \lfloor P\log_{10}2 \rfloor + 1$。
cmath
库中有函数 log10()
,直接使用即可。
然后考虑如何求最后500位数。
- 直接乘 $P$ 次,时间复杂度是 $500P = 1.5 \times 10^9$
- 用快速幂,时间复杂度是 $500^2\log P = 5 \times 10^6$
因此我们选择第二种方法。
时间复杂度
算法瓶颈在于求用快速幂 + 高精度,计算量是 $O(500^2 \log P)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 510;
int a[N], c[N], res[N];
void mul(int a[N], int b[N], int res[N])
{
memset(c, 0, N * 4);
for (int i = 0; i < 500; i ++ )
for (int j = 0; j < 500; j ++ )
if (i + j < 500)
c[i + j] += a[i] * b[j];
for (int i = 0, t = 0; i < 500; i ++ )
{
t += c[i];
res[i] = t % 10;
t /= 10;
}
}
void qmi(int p)
{
res[0] = 1;
a[0] = 2;
while (p)
{
if (p & 1) mul(a, res, res);
mul(a, a, a);
p >>= 1;
}
res[0] -- ;
}
int main()
{
int p;
scanf("%d", &p);
printf("%d\n", int(log10(2) * p) + 1);
qmi(p);
for (int i = 499, j = 0; j < 10; j ++ )
{
for (int k = 0; k < 50; k ++, i -- )
printf("%d", res[i]);
puts("");
}
return 0;
}
求解高精度*高精度为什么是这样的,基础课没讲到。。
为什么需要这个 res[0] – ;
求位数, 用 库函数, 如何证明精度不会丢失?