题目链接
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。
最后一定要注意输出格式！！本人因此爆零。。
附代码
#include<iostream> //快速幂：2的p次方=（2的平方）的p/2次方 = （（2的平方）的平方）的 p/2/2次方......
#include<cstdio> // f存的就是底数——2,2的2次方，2的二次方的二次方......
#include<cmath> // res 存的就是最后的答案
#include<cstring> // sav是每一次高精度乘法的临时数组
using namespace std;
int p,f[],res[],sav[]; //数组开500多一点已足够
void rr1() { //rr1是将答案更新，乘上现在的底数
memset(sav,,sizeof(sav));
for(int i = ;i <= ; i++) //动手画一下 ，列一个竖式，就会发现[i]*[j]得到的数字其实是[i+j-1]位上的数字
for(int j = ;j <= ; j++) //这里只是乘，还没有进位
if(i+j<=) sav[i+j-] += res[i] * f[j];
for(int i = ;i <= ; i++) { //进位
sav[i+] += sav[i] / ;
sav[i] %= ;
}
memcpy(res,sav,sizeof(res)); //把求出来的数组sav更新到res中
}
void rr2() { //rr2求得是底数的平方的值，存在f中
memset(sav,,sizeof(sav)); //同上
for(int i = ;i <= ; i++)
for(int j = ;j <= ; j++)
if(i+j<=)sav[i+j-] += f[i] * f[j];
for(int i = ;i <= ; i++) {
sav[i+] += sav[i] / ;
sav[i] %= ;
}
memcpy(f,sav,sizeof(f));
}
int main() {
scanf("%d",&p);
printf("%d\n",(int)(log10() * p + )); //先输出位数
res[] = ;
f[] = ; //初始化要为2，否则会一直乘1
while(p != ) { //快速幂
if(p % == ) rr1(); //任何一个数一直/2最后一定是1，这样就能确保更新答案
p /= ; //rr1,rr2为高精度乘法
rr2(); //每一次都更新一遍f，也就是底数的平方
}
res[] -= ;
for(int i = ;i >= ; i--)
if(i != && i % == ) printf("\n%d",res[i]); //注意输出格式。
else printf("%d",res[i]);
return ;
}
AC代码
//NOIP2003普及组t4