0026-麦森数

问题描述

形如 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)

输出

第 1 行:十进制高精度数 2^p-1 的位数。
第 2-11 行:十进制高精度数 2^p-1 的最后 500(每行输出 50 位,共输出 10 行,不足 500 位时高位补 0)位数字。 不必验证 2^p-1 与 p 是否为素数。

输入样列

1279

输出样例

386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

解题思路

1. 求位数，有个固定的算法：(log2/log10)*p+1
   • loga(b)的结果k表示a的k次方等于b
   • 存在一个换底公式（自行百度）：loga(c)/logb(c)=logb(c)，pascal党可以通过ln（相当于是loge，e是自然底数）来实现任意底数的log
   • 显然log10（k）向上取整表示k的位数
   • log的运算满足规律loga（b*c）=loga（b）+loga（c）
   • 由4得出，loga（b^c）=loga（b）*c
   • 所以，log10（2）*n可以表示2^n的位数
2. 求后500位，做大整数加法

算法实现

using System;

namespace Questions{
    class Program{
        public static void Main(string[] args){
            int N = int.Parse(Console.ReadLine());
            int sumIndex = (int)(Math.Log10(2) * N + 1);
            Console.WriteLine(sumIndex);
            int[] temp = new int[500];
            int[] result = new int[500];
            result[0] = 1;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < 500; j++) {
                    int middle = result[j] * 2 + temp[j];
                    if (middle >= 10)
                    {
                        if (j != 499)
                            temp[j + 1]++;
                        temp[j] = middle - 10;
                    }
                    else {
                        temp[j] = middle;
                    }
                }
                result = temp;
                temp = new int[500];
            }
            result[0]--;
            for (int i = 0; i <500; i++) {
                Console.Write(result[499-i]);
                if ((i + 1) % 50 == 0)
                    Console.WriteLine();
            }
            Console.ReadKey();
        }
    }
}