首页 > 代码库 > 快速幂+分治（洛谷P1045 麦森数 noip2003）
快速幂+分治（洛谷P1045 麦森数 noip2003）
形如的素数称为麦森数，这时
一定也是个素数。但反过来不一定，即如果
是个素数，
不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是
，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入（
），计算
的位数和最后500位数字（用十进制高精度数表示）
文件中只包含一个整数（
）
第一行：十进制高精度数的位数。
第2-11行：十进制高精度数的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）
不必验证与
是否为素数。
输入样例#1：
1279
输出样例#1：
38600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
文库大神的解析
我就不多说了，放上代码~
#include<bits/stdc++.h>#define maxn 40000#define inf 999990using namespace std;int n;int ans[maxn],s[maxn];void solve(int x){ if(x==0) return ; solve(x/2); for(int i=1;i<=500;i++)//顺序从低到高高精度乘法 for(int j=1;j<=500;j++) { if(x%2==0) ans[i+j-1]+=s[i]*s[j]; else ans[i+j-1]+=s[i]*s[j]*2; } for(int i=1;i<=500;i++) { s[i]=ans[i]%10; ans[i+1]+=ans[i]/10; } memset(ans,0,sizeof(ans));//因为ans作为一个介质的功效，要随即清零 }int main(){ cin>>n; cout<<int(log(2)/log(10)*n+1)<<endl;//换底公式， s[1]=1;//important!!! solve(n); for(int i=500;i>=2;i--) { cout<<s[i]; if(i%50==1) cout<<endl; } cout<<s[1]-1<<endl; return 0;}
快速幂+分治（洛谷P1045 麦森数 noip2003）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。