526互联

洛谷P1045 麦森数。 快速幂算法以及固定位数的高精度乘法的优化

发布时间 2023-04-19 17:25:00作者: 凪风sama

P1045 [NOIP2003 普及组] 麦森数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 想法很简单，我们要做的就是两件事，求2^P-1的位数，求出2^P-1的最后500位数，也就是低五百位，500位想一想常规类型肯定存不下，int到10^9,long long 到10^18，于是只能用高精度乘法来算阶乘

  1.   第一步，可以不用通过求出所有2^P-1的数然后记录位数来得出其位数，给出几个例子

                         1000为四位数，位数=lg1000+1=3+1=4，同理对于5486，位数=int(lg5486)+1=4,所以对于一个数，只需要求他对10的对数值加上1就是其位数，对于这次的2^P-1,可以知道其尾数必为2的倍数，（0除外），因此2^P-1的位数即2^P的位数 

于是其位数=int(lg(2^P))+1=int(P*lg2)+1,这样看来只需要调用cmath头文件里的lg10函数求出lg2就可以直接得出位数

         2. 第二步，求出其后500位， 这里应用高精度乘法，但是由于只需要求500位，高于500位的数字其实并不用去关注，直接丢掉即可

const int MAX = 500;
typedef long long LL;//不用long long会爆掉的
void Big_Mul(LL* ans, LL* Base)
{
    LL C[MAX] = { 0 };
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            if(i+j<MAX)//高于500位直接舍弃
            C[i + j] += ans[i] * Base[j];
        }
    }
//下面是逐个位进位处理
//方便起见我们不设置进制位，而是让后一位数加上前一位数的进位值，然后前一位数舍弃其进位值来实现逐位进位
    for (int i = 0; i <MAX-1; i++)
    {
        C[i + 1] = C[i + 1] + C[i]/10;
        C[i] %= 10;//舍弃进位值
    }
    C[MAX - 1] %= 10;//舍弃最大为的进位值，因为只需要后五百位，多的位数不需要
    for (int i = 0; i < MAX; i++)
        ans[i] = C[i];//拷贝
}

只有高精度乘法，然后朴素乘方的话会TLE的，因此还要配合快速幂来加速

下面给出完整代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAX = 500;
typedef long long LL;
void Big_Mul(LL* ans, LL* Base)
{
    LL C[MAX] = { 0 };
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            if(i+j<MAX)
            C[i + j] += ans[i] * Base[j];
        }
    }
    for (int i = 0; i <MAX-1; i++)
    {
        C[i + 1] = C[i + 1] + C[i]/10;
        C[i] %= 10;
    }
    C[MAX - 1] %= 10;
    for (int i = 0; i < MAX; i++)
        ans[i] = C[i];
}
int main()
{
    int p;
    cin >> p;
    cout << int(log10(2.0) * p +1)<< endl;//求出位数并输出
    LL ans[MAX] = { 0 };
    LL Base[MAX] = { 0 };//高精度数组初始化
    ans[0] = 1;//结果存储
    Base[0] = 2;//基数也就是底数
    while (p)//快速幂
    {
        if (p & 1)
            Big_Mul(ans, Base);
        Big_Mul(Base, Base);//可以看到就是将快速幂里的乘法变为了高精度乘法
        p >>= 1;
    }
    ans[0]--;//求出2^P-1
        for (int i = 499; i >= 0; i--)//逆序输出500位
        {
                cout << ans[i];
                if(i%50==0)//每50位换行
            cout << endl;
        }
    return 0;
}