谈谈高精度计算的应用

哈喽各位亲爱的观众朋友们大家好！首先，或许是比较迟的祝各位圣诞快乐！（我们不都过1024吗？）近期，我发现我们班里不少人的麦森数这道题做的不是特别理想。所以今天我就以AC这道题的过来人的视角，出一期专栏，来探讨一下麦森数的难，究竟难在何处。让我们点开下面的音乐，开启今天的内容吧！（今日音乐《The truth that you leave》）

题目描述

形如（2^P）-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2^P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。

任务：从文件中输入P（1000 < P < 3100000），计算2^P-1的位数和最后500位数字（用十进制高精度数表示）。

输入格式

文件中只包含一个整数P（1000 < P < 3100000）。

输出格式

第一行：十进制高精度数2^P-1的位数；

第2-11行：十进制高精度数2^P-1的最后500位数字（每行输出50位，共输出10行，不足500位时高位补0）；

不必验证2^P-1与P是否为素数。

题目的意思很简单，就是要求出2的n次方的10进制后500位，以及这个数字一共有多少位。

根据一般人的想法，这个题的两项输出好像是有关联的。但是事实证明，若想不超时，这两项输出还真得分开来处理！

我们先来看一下1st token——求出这个数的位数。这时候我们高中数学里的对数就派上用场了！

这里说一下我个人用的一个不太完善的向下取整双精度数输出的方法：printf("%.0f",x-0.5);

然后我们进行高精度的计算。这里我们不少人会稍微的在草稿纸上画个图来帮助自己思考一下。但这时候画图出错就很容易误导大家了（别问我为什么，我也是在这里出错的）

而且事实上，我们只用算后500位就行了。往后的任何位数都是不影响输出结果的。这里面的原因需要大家联想一下我们小学学的乘法竖式原理。高精度计算的方法我们在前面已经讲过，在这里我们需要做一下改进，然后套在一个函数里随时调用。

题解如下（我突然发现B站专栏里居然还有代码块这个东西，简直是程序员的福音！）

#include
#include
#include
#include
using namespace std;
int now[500];
int in;
void cr(){//高精度数*2
	for(int a = 0;a<500;a++){
		now[a] = now[a] * 2;
	}for(int a = 499;a>0;a--){
		now[a-1]+=now[a]/10;
		now[a]=now[a]%10;
	}
}
void fn(){//高精度数据平方
	int ans[500];
	memset(ans,0,sizeof ans);
	int cw = 0;
	for(int a = 499;a>=0;a--){
		for(int b = 499;b>=0;b--){
		if(cw<=b){
			ans[b-cw]+=now[b]*now[a];
		}	
		}
		cw++;
	}for(int a = 499;a>0;a--){
		ans[a-1]+=ans[a]/10;
		ans[a]=ans[a]%10;
	}
	ans[0]=ans[0]%10;
	for(int a=0;a<500;a++){
		now[a]=ans[a];
	}
}
void sep(int fa){
	
	if(fa==1){
		cr();
		return ;
	}
	else {
		if(fa%2==0){
			sep(fa/2);
			fn();
		}
		else{
			sep(fa/2);
			fn();
			sep(1);
		}
	}
}

int main(){//
	memset(now,0,sizeof now);
	cin >> in;
	double cal;
	cal = in;
	printf("%.0f",(cal*0.301029995)+0.5);
	cout << endl;
	now[499]=1;
	sep(in);
	for(int a = 0;a<10;a++){
		for(int b = 0;b<50;b++){
			if((a*50)+b!=499)
			cout <

好啦，今天的题解到这里也就结束了。喜欢的话记得——一键三连。这期阅读超过50，我下期就再挑战一次小木棍！