题目描述

形如 2P−12^{P}-1 的素数称为麦森数，这时 PP 一定也是个素数。但反过来不一定，即如果 PP 是个素数，2P−12^{P}-1 不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是 P=3021377P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入 PP（1000<P<31000001000<P<3100000），计算 2P−12^{P}-1 的位数和最后500位数字（用十进制高精度数表示）。

输入格式

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

输出格式

第一行：十进制高精度数 2P−12^{P}-1 的位数。
第 2-11 行：十进制高精度数 2P−12^{P}-1 的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）。
不必验证 2P−12^{P}-1 与 PP 是否为素数。

输入输出样例

输入 #1

1
1279

输出 #1

1
2
3
4
5
6
7
8
9
10
11
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

说明/提示

【题目来源】
NOIP 2003 普及组第四题

思路

使用Java的BigInteger类。
可用高精度快速幂计算得到 2P−12^P-1，但是会MLE，因此需要一些小技巧。
位数=⌈lg⁡(2P−1)⌉位数=\lceil\lg(2^P-1)\rceil，由于 2P2^P 个位不为 00，因此 位数=⌈lg⁡2P⌉=⌈Plg⁡2⌉位数=\lceil\lg2^P\rceil=\lceil P\lg2\rceil。
题目要求输出后500位，那么就是对 1050010^{500} 取模，用高精度快速幂计算得到 (2P−1) mod 10500(2^P-1)\bmod 10^{500} 时间和内存都允许。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/******************************************************************
 * Copyright: 11D_Beyonder All Rights Reserved 
 * Author: 11D_Beyonder 
 * Problem ID: Luogu P1045 
 * Date: 2021 Mar. 13th 
 * Description: BigInteger
 *******************************************************************/

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	private static BigInteger mod;

	private static void init() {
		String s = new String("1");
		for (int i = 1; i <= 500; i++) {
			s += '0';
		}
		mod = new BigInteger(s);
	}

	private static BigInteger quickPow(int b) {
		BigInteger a = BigInteger.valueOf(2);
		BigInteger res = BigInteger.ONE;
		while (b > 0) {
			if ((b & 1) == 1) {
				res = res.multiply(a).mod(mod);
			}
			a = a.multiply(a).mod(mod);
			b >>= 1;
		}
		return res;
	}

	public static void main(String[] args) {
		init();
		Scanner scanner = new Scanner(System.in);
		int p = scanner.nextInt();
		scanner.close();
		char[] s = quickPow(p).subtract(BigInteger.ONE).toString().toCharArray();
		System.out.println((int) Math.ceil(p * Math.log10(2)));
		int line = 0;
		for (int i = s.length - 500; i < s.length; i++) {
			if (i < 0) {
				System.out.print('0');
			} else {
				System.out.print(s[i]);
			}
			line++;
			if (line == 50) {
				System.out.print('\n');
				line = 0;
			}
		}
	}
}