蓝桥杯 算法训练 麦森数 By Assassin (数学+模拟)

2019-04-13 16:21发布

站内文章 / 模拟电子
13099 0 1030
问题描述 　　形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。 　　任务：从文件中输入P（1000 思路：题目本身的难点就是一个数学知识，麦森数长度怎么求，网上看到别人的思路才知道
length=p∗log10(2)+1 至于求后500位，就是一个大数乘法模拟，乘法要用快速幂，我用的数组加string串模拟。注意的就是数组直接用500长度的就行！不用结果是否超过500.知识点都不难（除了数学…）就是组合一下。
再次体会到了数学的力量啊… #include using namespace std; string quick[26]; string multi(string a,string b){ int temp1[502]={0},temp2[501]={0},answer[501]={0}; int lena=a.size(),lenb=b.size(); for(int i=1;i<=lena;i++){ if(i>500) break; temp1[i]=(a[lena-i]-'0'); } for(int i=1;i<=lenb;i++){ if(i>500) break; temp2[i]=(b[lenb-i]-'0'); } for(int i=1;i<=500;i++){ for(int j=1;j<=500;j++){ if(i+j-1<=500){ answer[i+j-1]+=temp1[i]*temp2[j]; } } } for(int i=1;i<=500;i++){ answer[i+1]+=(answer[i])/10; answer[i]%=10; } string ans=""; for(int i=500;i>=1;i--){ ans+='0'+answer[i]; } return ans; } int main(){ int n; quick[0]="2"; for(int i=1;i<=25;i++){ quick[i]=multi(quick[i-1],quick[i-1]); } scanf("%d",&n); string ans="1"; for(int i=0;i<=25;i++){ if(n>>i&1){ ans=multi(ans,quick[i]); } } // cout< for(int i=500;i>=3;i--){ if(ans[i]>='0'){ ans[i]--; break; } else{ ans[i]='9'; } } cout<<(int)(n*log10(2))+1<for(int i=0;i<10;i++){ for(int j=0;j<50;j++){ cout<50+j]; } cout<return 0; }

热门文章