From 364f59c007db4a98bc4bc93f5346fc9b4a0a616a Mon Sep 17 00:00:00 2001
From: luoguyuntianming <46839655+luoguyuntianming@users.noreply.github.com>
Date: Sun, 14 Jul 2019 15:19:50 +0800
Subject: [PATCH] =?utf8?q?=E6=B7=BB=E5=8A=A0=EF=BC=9A=E9=AB=98=E7=B2=BE?=
 =?utf8?q?=E5=BA=A6=E5=BF=AB=E9=80=9F=E5=B9=82?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 docs/math/quick-pow.md | 59 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)

diff --git a/docs/math/quick-pow.md b/docs/math/quick-pow.md
index 6bcb572b..872a7048 100644
--- a/docs/math/quick-pow.md
+++ b/docs/math/quick-pow.md
@@ -87,3 +87,62 @@ long long qpow(long long a, long long b, long long p) {
 ??? note "例题"
 
     做一做[Luogu P1226](https://www.luogu.org/problemnew/show/P1226)
+
+## 高精度快速幂
+
+??? note "前置技能"
+     请先学习[高精度](https://oi-wiki.org/math/bignum/)
+
+??? note "例题【NOIP2003普及组改编·麦森数】（[原题在此](https://www.luogu.org/problemnew/show/P1045)）"
+     题目大意：从文件中输入P（1000<P<3100000），计算 $2^P−1$ 的最后100位数字（用十进制高精度数表示），不足100位时高位补0。
+
+### 例题代码
+
+```cpp
+  #include<bits/stdc++.h>
+ using namespace std;
+ int a[505],b[505],t[505],i,j;
+ int mult(int x[],int y[])//高精度乘法
+ {
+ 	memset(t,0,sizeof(t));
+ 	for(i=1;i<=x[0];i++)
+ 	{
+ 		for(j=1;j<=y[0];j++)
+ 		{
+ 			if(i+j-1>100) continue;
+ 			t[i+j-1]+=x[i]*y[j];
+ 			t[i+j]+=t[i+j-1]/10;
+ 			t[i+j-1]%=10;
+ 			t[0]=i+j;
+ 		}
+ 	}
+ 	memcpy(b,t,sizeof(b));
+ }
+ void ksm(int p)//快速幂
+ {
+ 	if(p==1) 
+ 	{
+ 		memcpy(b,a,sizeof(b));
+ 		return;
+ 	}
+ 	ksm(p/2);
+ 	mult(b,b);
+ 	if(p%2==1) mult(b,a);
+ }
+ int main()
+ {
+ 	int p;
+ 	scanf("%d",&p);
+ 	a[0]=1;a[1]=2;
+ 	b[0]=1;b[1]=1;
+ 	ksm(p);
+ 	for(i=100;i>=1;i--)
+ 	{
+ 		if(i==1) 
+ 		{
+ 			printf("%d\n",b[i]-1);
+ 		}
+ 		else printf("%d",b[i]);
+ 	}
+ }
+```
-- 
2.11.0