传送门
这道题纯粹是考数学。编程复杂度不大（别看我写了一百多行其实有些是可以不必写的）。
计算位数不必用高精时刻存，不然可想而知时间复杂度之大。首先大家要知道一个数学公式 logn(a*b)=logn(a)+logn(b)至于证明翻数学书吧。而且，用log10(n)+1即可求出n的位数。
则2^p的位数=log10(2^p)+1=p*log10(2)+1。这样，我们算的时候就不必随时存着位数了。
但是，如果直接写高精和n次循环，时间复杂度依旧很高。所以我们就要用快速幂。幂的运算是初中内容，几个公式如下:n^a*n^b=n^(a+b)，(n^a)^b=n^(a*b)。
所以，我们就可以将乘方的复杂度优化成O(logn)了。
代码
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> using namespace std; const int MAXN = 2001; char c[MAXN]; inline char *read() struct Big_int inline void operator = (char *c) inline void operator = (int x) } inline void print() puts(""); } }; inline Big_int operator + (const Big_int x, const Big_int y) while(!ret.s[ret.idx 1] && ret.idx > 1) ret.idx; return ret; } inline bool operator < (const Big_int x, const Big_int y) inline Big_int operator (Big_int x, Big_int y) ret.s[i] = x.s[i] y.s[i]; } while(!ret.s[ret.idx 1] && ret.idx > 1) ret.idx; return ret; } inline Big_int operator * (const Big_int x, const Big_int y) while(!ret.s[ret.idx 1] && ret.idx > 1) ret.idx; return ret; } int p; Big_int a, ans; int main() a = 1; ans = ans a; ans.idx = 500; ans.print(); return 0; }
上一篇：[luoguP1022] 计算器的改良（模拟）
下一篇：[luoguP1042] 乒乓球（模拟）
高精度 快速幂
