[luoguP1045] 麦森数（快速幂 + 高精度）

传送门

这道题纯粹是考数学。编程复杂度不大（别看我写了一百多行其实有些是可以不必写的）。

计算位数不必用高精时刻存，不然可想而知时间复杂度之大。首先大家要知道一个数学公式 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; }

　　

上一篇：[luoguP1854] 花店橱窗布置（DP）

下一篇：[luoguP1042] 乒乓球（模拟）

---

高精度 快速幂