题目链接
https://www.luogu.org/problemnew/show/P1045
题目大意
本题目的主要意思就是给定一个p,求2-1的位数和后500位数。
解题思路
首先看一下数据范围,我们不难发现此题必须要用高精度来做。但是每一次高精度乘法的复杂度是o(n)的(n为数字的位数),所以很显然需要加一个快速幂。但是事实证明快速幂+高精度也会超时,所以我们必须进一步优化时间。
根据题意,我们可知,只需要记录下后500位数即可,这里牵扯到一点点数论的知识,这一个数字的后500位是与500位以外的数是没有一点关系的,根据这个性质,我们就可以开一个500大的数组,每一次记录后500位的数字即可。
但是此题还有一个难点,就是求总的位数,这里要运用数论知识。
我们不难发现,2的最后一位不可能是0,所以2和2的位数是一样的,我们只需求出2的位数即可。
我们知道,如果某个数是10,那么这个数就有n+1位数字。我们知道,log10(2)意思是10的多少次方=2,所以10=2。所以我们把2写成(10),再根据幂的平方运算法则写成10,而10的位数是log10(2)*p+1,也就是2的位数是log10(2)*p+1,也就是2-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