[NOIP2003普及组]麦森数(快速幂+高精度)
[NOIP2003普及组]麦森数(快速幂+高精度)
Description
形如2^P-1的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,2^P-1不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。
任务:从文件中输入P(1000 < P < 3100000),计算2^P-1的位数和最后500位数字(用十进制高精度数表示)Input
只包含一个整数P(1000 < P < 3100000)
Output
第一行:十进制高精度数2^P-1的位数。
第2-11行:十进制高精度数2^P-1的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)
不必验证2^P-1与P是否为素数。Sample Input
1 1279Sample Output
1234567891011 38600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
题目大意:计算2^P-1的位数和它的最后500位并输出。
1、计算位数:2^P-1的位数为[log10(2^P)]+1==[Plog10(2)]+1
2、计算最后500位:高精度预处理2^i,计算时将P分解成二进制形式,然后相乘,只保留500位
3、网站上的似乎和原题不太一样,原题要求每输出50位换行
倍增快速幂+高精(果然什么东西跟高精扯上就恶心了)
只保留最后500位,前面的直接卡掉
位数可以直接算出来,n进制数M的位数是log(n)M,那么log(10)2^p=p*log(10)2=p*(log(2)/log(10))
1、肯定需要高精度,毕竟500位
2、普通乘法肯定超时,乘法次数*位数
因为位数=plog(10)2=310W*log2
操作次数为=310W
所以普通乘法的复杂度为:n^2,这肯定要炸的不能在炸。
如果是保留500位,那也是500*310W,也要超,所以这里一定要用到快速幂
本题分两问,第一问求位数,可以证明:当x有n位时,必有10^(n-1)<=x<10^n(如x有3位时必有100=10^2<=x<1000=10^3),取常用对数,n-1<=lgx<n,即lgx的整数部分是n-1,也就是说数x的位数是lg(x)的整数部分+1。故欲求x的位数只需求floor(log10(x)+1).
然后第二问是去掉了取模运算、用上高精度的快速幂:
#include <bits/stdc++.h>
using namespace std;
void mul(int x[],int y[]);
int main()
{
long p;
int num=;
int ans[]={},a[]={},i;
freopen("mason.in","r",stdin);
freopen("mason.out","w",stdout);
scanf("%ld",&p);
//第一问ok
num=(int)floor(p*log10()+);
printf("%d\n",num); /*快速幂求2^p,同时用高精度乘法*/
ans[]=; a[]=;
while(p>)
{
if(p&) //if(p%2==1)
mul(ans,a);
p=p>>; //p=p/2;
mul(a,a); //a*a -> a
}
ans[]-=; //这个地方其实直接减1会有bug。当ans[1]为0的时候是错误的结果。所以可以采用下面的方法减1。但是对这个题目而言,2^p-1必然是奇数,也即个位是不可能为0。(ans[1]不会为0.)
/*for(i=1;i<=500;i++)
{
if(ans[i]>0) {ans[i]--;break;}
}
for(;i>=1;i--) ans[i]=9;*/
for(i=;i>;i--) {printf("%d",ans[i]); if((i-)%==) printf("\n");}
printf("\n");
return ;
}
void mul(int x[],int y[])
{
/* x*y->x */
int tmp[]={},lx=,ly=,i,j,len; //tem[]一定要清零。
//memset(tmp,0,sizeof(tmp));
while(x[lx]==&&lx>) lx--; //计算x首位位置
while(y[ly]==&&ly>) ly--; //计算y首位位置
len=lx+ly;
for(i=;i<=ly;i++)
for(j=;j<=lx;j++)
if(i+j-<=) tmp[i+j-]+=y[i]*x[j]; //if语句是保证只保留500位
for(i=;i<=;i++)
{
tmp[i+]+=tmp[i]/; //把进位的值加到高位
tmp[i]%=;
/*if(i<500&&tmp[i+1]==0)
{len=i; break;}*/ //这个地方没理解其用意,似乎只是优化循环次数。但len没有使用的机会,所以干脆删除掉比较好。
}
for(i=;i>;i--) x[i]=tmp[i]; //把结果复制到x数组
}
最新文章
- Windows Phone 二十一、联系人存储
- Effective C++ -----条款47:请使用traits classes表现类型信息
- UnixBench测试
- Systematic LncRNA Classification
- Delphi 设置WebBrowser 代理服务器 与 UserAgent
- jdk源码调试功能
- Mongo的导出工具mongoexport介绍
- 关于Qt的灵异错误
- Oracle树反向查询的优化(转载)
- 关于UTF8文件带BOM头可能会引起的错误解析
- input标签的美化
- Coursera, Big Data 3, Integration and Processing (week 5)
- windows配置Erlang环境
- script标签
- ERROR org.redisson.client.handler.CommandDecoder - Unable to decode data. channel
- PetaPoco源代码学习--2.TableInfo、ColumnInfo类和Cache类
- ASPX代码加固小结
- Spring boot 遇到了连接mysql的错误
- [BAT]批处理自动修改区域和语言选项
- CentOS7 初始化配置