洛谷P1045 麦森数

小鱼儿 2022-05-30 11:08 234阅读 0赞

## 题目描述 ##

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

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

## 输入输出格式 ##

输入格式：

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

输出格式：

第一行：十进制高精度数2^\{P\}-12*P*−1 的位数。

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

不必验证2^\{P\}-12*P*−1 与P

*P* 是否为素数。

![70][]

弱鸡写的50分裸的高精度

刚开始还想能不能每次乘16（2^4），然后再乘（P%4）个2,试了试，果然还是5个TLE

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<math.h>
    using namespace std;
    
    int ans[909527] = { 1, 1 };
    int P;
    
    void HighMulity(int k)
    {
    	int tmp=0;
    	for (int i = 1; i <= ans[0]; i++)
    	{
    		ans[i] = tmp + ans[i] * k;
    		tmp = ans[i] / 10;
    		ans[i] %= 10;
    		if (tmp>0&&i>=ans[0])
    		{
    			ans[0]++;
    		}
    	}
    }
    
    
    void MinusOne()
    {
    	for (int i = 1; i <= ans[0]; i++)
    	{
    		if (ans[i] >= 1)
    		{
    			ans[i] -= 1;
    			break;
    		}
    		else
    		{
    			ans[i] = 9;
    			ans[i + 1] -= 1;
    		}
    	}
    }
    
    void print()
    {
    	int len = P*log10(2) + 1;
    	cout << len << '\n';
    	int num = 0;
    	for (int i = 500; i >= 1; i--)
    	{
    		cout << ans[i];
    		num++;
    		if (num % 50 == 0)
    			cout << '\n';
    	}
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> P;
    	int num = P / 4;
    	int left = P % 4;
    	for (int i = 0; i < num; i++)
    	{
    			
    		HighMulity(16);
    		
    	}
    	for (int i = 0; i < left; i++)
    	{
    		HighMulity(2);
    
    	}
    	
    
    	MinusOne();
    	print();
    	return 0;
    }

正确解法：

快速幂+高精度

有一个公式能够直接计算2^P-1的位数：log10(2)\*P+1

快速幂详解见下面第一个链接(强烈建议先看第一个链接，因为我直接看第二个链接没懂，看了第一个才知道数组代表着什么)

然后高精度的做法就是前500位模拟竖式

这是一篇讲快速幂很好的文章

[http://blog.csdn.net/ReidSC/article/details/64651804][http_blog.csdn.net_ReidSC_article_details_64651804]

参考题解：

[https://www.luogu.org/blog/Future37/solution-p1045][https_www.luogu.org_blog_Future37_solution-p1045]

我把题解链接中的高精度乘法的函数模块化了，题解中用到了一个memcpy函数，但当我传入参数时不管用，所以我只能循环遍历复制数组。不信的话你可以看看题解中的高精度乘法函数。

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<math.h>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    using namespace std;
    
    int ans[1001];//答案
    int a[1001];
    int tmp[1001];//乘法的话数组开2倍
    
    void HighMulity(int *a,int *b)
    {
    	memset(tmp, 0, sizeof(tmp));
    	for (int i = 1; i <= 500; i++)//只算前500位的乘积
    	for (int j = 1; j <= 500; j++)
    		tmp[i + j - 1] += a[i] * b[j];
    	for (int i = 1; i <= 500; i++)//单独考虑进位
    		tmp[i + 1] += tmp[i] / 10, tmp[i] %= 10;
    	
    	for (int i = 0; i < 1001; i++)//将结果复制给a数组,注意，此处是给参数a数组，不是全局变量a数组
    		a[i] = tmp[i];
    }
    
    void print()
    {
    	int num = 0;//倒序打印
    	for (int i = 500; i >= 1; i--)
    	{
    		cout << ans[i];
    		num++;
    		if (num % 50 == 0)
    			cout << '\n';
    	}
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	int P;
    	cin >> P;
    	printf("%d\n", (int)(log10(2)*P + 1));//计算位数公式
    	a[1] = 2;
    	ans[1] = 1;
    	while (P)//快速幂,强烈建议先看第一个链接，这样就知道每个数组代表什么
    	{
    		if (P % 2 == 1)
    		{
    			HighMulity(ans,a);
    		}
    		P /= 2;
    		HighMulity(a,a);
    	}
    	ans[1] -= 1;
    	print();
    	return 0;
    }

[70]: /images/20220530/516f7ebe5a5444d3a1041223c69bae9b.png
[http_blog.csdn.net_ReidSC_article_details_64651804]: http://blog.csdn.net/ReidSC/article/details/64651804
[https_www.luogu.org_blog_Future37_solution-p1045]: https://www.luogu.org/blog/Future37/solution-p1045