题目描述
形如 2P−1 的素数称为麦森数,这时 P 一定也是个素数。但反过来不一定,即如果 P 是个素数,2P−1 不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是 P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。
任务:从文件中输入 P(1000<P<3100000),计算 2P−1 的位数和最后500位数字(用十进制高精度数表示)。
输入格式
文件中只包含一个整数 P(1000<P<3100000)。
输出格式
第一行:十进制高精度数 2P−1 的位数。
第 2-11 行:十进制高精度数 2P−1 的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)。
不必验证 2P−1 与 P 是否为素数。
输入输出样例
输入 #1
输出 #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−1,但是会MLE,因此需要一些小技巧。
位数=⌈lg(2P−1)⌉,由于 2P 个位不为 0,因此 位数=⌈lg2P⌉=⌈Plg2⌉。
题目要求输出后500位,那么就是对 10500 取模,用高精度快速幂计算得到 (2P−1)mod10500 时间和内存都允许。
代码
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
|
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; } } } }
|