题目链接：https://www.luogu.org/problemnew/show/P1045 题目意思：本题目的主要意思就是给定一个p，求2p-1的位数和后500位数。 解题思路：
首先看一下数据范围，我们不难发现此题必须要用高精度来做。但是每一次高精度乘法的复杂度是o(n)的（n为数字的位数），所以很显然需要加一个快速幂。但是事实证明快速幂+高精度也会超时，所以我们必须进一步优化时间。
根据题意，我们可知，只需要记录下后500位数即可，这里牵扯到一点点数论的知识，这一个数字的后500位是与500位以外的数是没有一点关系的，根据这个性质，我们就可以开一个500大的数组，每一次记录后500位的数字即可。
但是此题还有一个难点，就是求总的位数，这里要运用数论知识。
我们不难发现，2n的最后一位不可能是0，所以2p和2p-1的位数是一样的，我们只需求出2p的位数即可。
我们知道，如果某个数是10n，那么这个数就有n+1位数字。我们知道，log10(2)意思是10的多少次方=2，所以10log10(2)=2。所以我们把2p写成（10log10(2) )p，再根据幂的平方运算法则写成10log10(2)*p，而10log10(2)*p的位数是log10(2)*p+1，也就是2p的位数是log10(2)*p+1，也就是2p-1的位数是log10(2)*p+1。
最后一定要注意输出格式！！本人因此爆零。。
附代码：
1 #include<iostream> //快速幂：2的p次方=（2的平方）的p/2次方 = （（2的平方）的平方）的 p/2/2次方...... 2 #include<cstdio> // f存的就是底数——2,2的2次方，2的二次方的二次方...... 3 #include<cmath> // res 存的就是最后的答案 4 #include<cstring> // sav是每一次高精度乘法的临时数组 5 using namespace std; 6 int p,f[510],res[510],sav[510]; //数组开500多一点已足够 7 void rr1() { //rr1是将答案更新，乘上现在的底数 8 memset(sav,0,sizeof(sav)); 9 for(int i = 1;i <= 500; i++) //动手画一下 ，列一个竖式，就会发现[i]*[j]得到的数字其实是[i+j-1]位上的数字 10 for(int j = 1;j <= 500; j++) //这里只是乘，还没有进位 11 if(i+j<=505) sav[i+j-1] += res[i] * f[j]; 12 for(int i = 1;i <= 500; i++) { //进位 13 sav[i+1] += sav[i] / 10; 14 sav[i] %= 10; 15 } 16 memcpy(res,sav,sizeof(res)); //把求出来的数组sav更新到res中 17 } 18 void rr2() { //rr2求得是底数的平方的值，存在f中 19 memset(sav,0,sizeof(sav)); //同上 20 for(int i = 1;i <= 500; i++) 21 for(int j = 1;j <= 500; j++) 22 if(i+j<=505)sav[i+j-1] += f[i] * f[j]; 23 for(int i = 1;i <= 500; i++) { 24 sav[i+1] += sav[i] / 10; 25 sav[i] %= 10; 26 } 27 memcpy(f,sav,sizeof(f)); 28 } 29 int main() { 30 scanf("%d",&p); 31 printf("%d\n",(int)(log10(2) * p + 1)); //先输出位数 32 res[1] = 1; 33 f[1] = 2; //初始化要为2，否则会一直乘1 34 while(p != 0) { //快速幂 35 if(p % 2 == 1) rr1(); //任何一个数一直/2最后一定是1，这样就能确保更新答案 36 p /= 2; //rr1,rr2为高精度乘法 37 rr2(); //每一次都更新一遍f，也就是底数的平方 38 } 39 res[1] -= 1; 40 for(int i = 500;i >= 1; i--) 41 if(i != 500 && i % 50 == 0) printf("\n%d",res[i]); //注意输出格式。 42 else printf("%d",res[i]); 43 return 0; 44 }