曾彪彪的个人博客 -- P1045 [NOIP 2003 普及组] 麦森数（快速幂取模+高精)

# P1045 [NOIP 2003 普及组] 麦森数  （快速幂取模+高精)

## 题目描述

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

## 输出格式

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

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

不必验证 $2^{P}-1$ 与 $P$ 是否为素数。

## 输入输出样例 #1

### 输入 #1

```
1279
```

### 输出 #1

```
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
```

## 说明/提示

**【题目来源】**

NOIP 2003 普及组第四题

该题第一次直接使用高精算法，得分50分，原因是因为数据量太大了（输入数据有756839），运行超时。后面尝试使用快速幂，还是超时，后来经过调研，查阅资料，终于找到AC解法。

此题分两步，
- 第一步，计算2^p-1的次数。
因为2的n次方，尾数只可能是2，4，6，8，所以2^p-1的位数与2^p的位数相同。我们假设2^p的位数是n，也就是10^(n-1)。 因为1位是10^0，2位是10^1。
那么由2^p=10^(n-1)得出n-1=log10(2^p)，根据对数计算规则，得到n-1=p*log10(2)，求得n=p*log10(2)+1，直接输出即可。
- 第二部，输出2^p-1的后500位，不足500位，前面补0，并且每行输出50个字符。
  这个知识点之前我不会，不过上网调研了一下，搞明白了。这里需要弄明白几个知识点：
  1. 高精度乘法，这个之前我会，忽略。
  2. 快速幂，当计算一个数a的b次方是，如果一直连乘，那么复杂度是o(b)=o(n)。如果使用快速幂，可以把复杂度将到o(log(n))，具体分析如下：
   
   - ans=a^b，这里分情况讨论，
     - 当b为偶数时，ans=a^(b/2)*a^(b/2)=(a^(b/2))^2;
     - 当b为奇数时，ans=a*a^(b-1)=a*a^((b-1)/2)*a^((b-1)/2)=a*(a^((b-1)/2)^2)
   - 有了这个结论，就可以实现快速幂算法，递归代码如下：

```c++
        long fastPow(long a, long b){
            if(b==0){
                return 1;
            }
            if(b&1){ // b是奇数
                return a*fastPow(a,b-1);
            }
            long t=fastPow(a,b>>1); //b>>1是b/2的意思
            return t*t;
        }
    ```
    但是递归有时候会爆栈，所以更推荐迭代算法：
    ```c++
    long fastPow(long a, long b){
        long ans=1;
        while(b>0){
            if(b&1){
                ans=ans*a;
            }
            a=a*a;
            b=b>>1;
        }
    }

```

因为快速幂计算数字一般很大，造成long类型也存不下，并且我们一般不关心快速幂计算的值，只关心它的余数，所以就有了一个快速幂取模算法。
    快速幂取模算法的数学理论基础是：
    (a*b)%m=(a%m)*(b%m)%m;
    这个公式的推导如下：
    a=km+r，其中r=a%m，k是商
    b=lm+s，其中s=b%m，l是商。
    那么(a*b)%m=[(km+r)*(lm+s)]%m=(klm*m + ksm +lrm + rs)%m
    因为klm*m + ksm +lrm都是m的倍数，所以它们模m都等于0，所以上式=r*s%m=[(a%m)*(b%m)]%m

有了这个理论基础后，那么可以得出如下公式：
    - a^b%m=(a%m)^b%m
    - (a^b)%m=(a^(b/2)%m * a^(b/2)%m)%m  b是偶数   (等式1)
    - (a^b)%m=(a%m * a^(b-1/2)%m * a^(b-1/2)%m)%m  b是奇数   (等式2)

有了上面的结论，就可以实现快速幂取模方法了，代码如下：

```c++
    long fastPow(long a, long b, long mod){
        long ans=1;
        a=a%mod;
        while(b>0){
            if(b&1){
            ans=ans*a%mod;  //依据等式1
            }
            a=a*a%mod;  //依据等式2
            b=b>>1;
        }
        return ans%mod;        
    }
    ```

把以上知识点全部弄明白之后，就可以直接写本题的代码了。

```c++
    /**
    start time: 8:45
    End time:
    Type: simulator
    Solution:
    -
    1
    2
    10
    1279

-
    -
    test case:
    -
    -
    -
    -
    first submit score: 100
    cause:

**/

#include <bits/stdc++.h>
    using namespace std;

string multiple(string a, string b)
    {
        vector<int> result(a.size() + b.size(), 0);
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        for (int i = 0; i < a.size(); i++)
        {
            for (int j = 0; j < b.size(); j++)
            {
                int v = result[i + j] + (a[i] - '0') * (b[j] - '0');
                result[i + j] = v % 10;
                result[i + j + 1] += v / 10;
            }
        }
        bool leadingZeroFlag = true;
        string ans = "";
        for (int i = result.size() - 1; i >= 0; i--)
        {
            if (leadingZeroFlag)
            {
                if (result[i] == 0)
                {
                    continue;
                }
                leadingZeroFlag = false;
            }
            ans.push_back('0' + result[i]);
        }
        return ans;
    }

string getMod(string v, long mod)
    {
        string result = v;
        if (v.size() > mod)
        {
            result = v.substr(v.size() - mod, mod);
        }
        return result;
    }

string fastPow(long a, long b, long mod)
    {
        string ans = "1";
        string sa = to_string(a);
        while (b > 0)
        {
            if (b & 1)
            {
                ans = multiple(ans, sa);
                ans = getMod(ans, mod);
            }
            sa = multiple(sa, sa);
            sa = getMod(sa, mod);
            b = b >> 1;
        }
        ans[ans.size() - 1] = ans[ans.size() - 1] - 1;
        if (ans.size() < 500)
        {
            ans = string(500 - ans.size(), '0') + ans;
        }
        return getMod(ans, mod);
    }

int main()
    {
        // freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin);
        int p, count;
        cin >> p;
        count = p * log10(2) + 1;
        cout << count << endl;
        string ans = fastPow(2, p, 500);
        int c = 0;
        for (auto s : ans)
        {
            cout << s;
            c++;
            if (c >= 50)
            {
                cout << endl;
                c = 0;
            }
        }
        return 0;
    }

```

---

P1045 [NOIP 2003 普及组] 麦森数 （快速幂取模+高精)

评论(0)

P1045 [NOIP 2003 普及组] 麦森数（快速幂取模+高精)