麦森数（洛谷P1045题题解，Java语言描述）

题目要求

题目链接

分析

这题挺经典的，快速幂取模算法，如果求出大数再取模就可能T掉。

之前有篇文章写了这个算法：《快速幂算法详解&&快速幂取模算法详解》

既然是Java，那就要使用出Java的特点！BigInteger还在呢，都不必手写快速幂。 记住，哪怕是使用快速幂的pow再mod也会炸，所以使用modPow()，直接把模求出来。

你可能会怀疑， ( 2 P − 1 ) m o d ( 1 0 500 ) (2^{P}-1)mod(10^{500}) (2P−1)mod(10500)？ 是的，这个式子可以化为： ( 2 P ) m o d ( 10 500 ) − 1 (2^{P})mod({10}^{500})-1 (2P)mod(10500)−1，写成代码就是：TWO.modPow(p, 10.pow(500)).substract(1)。 注意上面的数字是代指，其实基本全是BigInteger对象。

你觉得恍然大悟？ 其实不对，做个比方：2…00000000，中间有1000个0，末尾500位全是0，那怎么办，得到的不是0吗？0-1就是-1？？取模得了-1？ 对吧，思考要深入！ 所以我们的代码错了吗？

也不是，首先要清楚的是，假设先取幂再取模，底数一定是2的幂次。 我们看一看2的幂次：2、4、8、16、32、64、128、256、512、1024、2048… 规律就是，末尾一定是2、4、8、6在循环，所以不可能是0啊！ 那我们这么做就是对的！

好，解决了求幂取模的问题，接下来是，你直接用了快速幂取模，没求幂次，怎么得到 2 P − 1 2^P-1 2P−1的位数？ 首先我们知道 2 P − 1 2^P-1 2P−1与 2 P 2^P 2P有着相同的位数（因为2的幂次末位不为零，所以 2 P 2^P 2P减去1，位数并不会改变），所以我们可以直接求 2 P 2^P 2P的位数。 我们不妨设 2 P = k 2^P=k 2P=k， 1 0 n 10^n 10n位数为 ( n + 1 ) (n+1) (n+1)，只需换底为10，幂次+1即为所求。 2 = 1 0 l g 2 2=10^{lg2} 2=10lg2 => 2 P = ( 1 0 l g 2 ) P = 1 0 p ∗ l g 2 = k 2^P=(10^{lg2})^P=10^{p*lg2}=k 2P=(10lg2)P=10p∗lg2=k 所以位数就是 p ∗ l g 2 + 1 p*lg2+1 p∗lg2+1，代码表示就是(int)(Math.log10(2)*p)+1

接下来讲代码编写的注意事项，稍有不注意就会爆炸：

• BufferedReader一定要用，否则必炸四个点好像是
• 不要用String去操作，用BigInteger很稳
• 不要直接取模，用快速幂取模
• 所有的补位和拼接全用StringBuilder
• 不要分次输出，尽量一次输出
• 连接\n的时候用单引号比较好
• 洛谷识别ONE但不识别TWO，所以必须换成new BinInteger(“2”)
• 求BigInteger对象的位数不能用bitLength()，那是二进制位数；可以使用toString()后的length()来求
• ……

有一说一，这题用Java写，操作性蛮强的。

测试数据1： in 756839 out 227832 18288448825429774219846956862417770870640302475247 92828312585598040121588421297674731878093115313182 16753914541797571068392534875840214937021204750378 89055619401647443568291937923950889819022384242323 28767636683196318572845992994357198238764218257600 09234774987448978769799124034384499030364505405943 84275497234460834579807796823701486980464630401353 54915833132974601389482848422119619724789014565809 44396409267168409183491136926492417685905113427201 26927068487680404055813342880902603793328544677887

测试数据7： in 607 out 183 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000531137992816767098689588206552468 62732959311772703192319944413820040355986085224273 91625022652292856688893294862465010153465793376527 07239409519978766587351943831270835393219031728127

AC代码（Java语言描述）

import static java.math.BigInteger.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String p = reader.readLine();
        BigInteger num = new BigInteger("2").modPow(new BigInteger(p), new BigInteger("10").pow(500)).subtract(ONE);
        reader.close();
        int length = num.toString().length();
        StringBuilder result = new StringBuilder();
        if (length