题目内容

P1045

大意:求 2^p-1 的位数和最后 500 位

解题思路

嗯,我的第一思路是爆算(不可能)

蒟蒻发现了求位数可以这样搞:由于 2^p 的各位不可能为 0,所以 2^p 的位数与 2^p-1 的位数相同。又由于一个数的位数为 \lg x+1 ,对 \lg(2^p)+1 进行变换可得

\lg(2^p)+1=p\lg2+1

然后于是第一问 O(1) 解决

第二问一看求 2^p-1 的后五百位,快速幂解决即可,每次操作使用 vector 的 resize() 函数来将多余的删掉即可。每次乘法的时候只乘 500 .

坑点:输出要求前导零和分行输出我因为后面那个调了好久

vector 的 resize 的用法:vector<int>::resize(std::size_t __new_size, const int &__x)意思就是将这个 vector 缩减/增加到能容纳 __new_size 个元素,第二个参数就是将增加出来的赋默认值

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef vector<int> bigint;

bigint operator*(bigint a, bigint b)//高精乘法
{
    bigint ans;
    int la=a.size()>500?500:a.size(),lb=b.size()>500?500:b.size();
    for(int i=0;i<la+lb;i++)
        ans.push_back(0);
    for(int i=0;i<lb;i++)
    {
        for(int j=0;j<la;j++)
        {
            ans[i+j]+=a[j]*b[i];
            if(ans[i+j]>=10)
            {
                ans[i+j+1]+=ans[i+j]/10;
                ans[i+j]%=10;
            }
        }
    }
    for(int i=ans.size()-1;i>0;i--)
    {
        if(ans[i])
            break;
        else
            ans.pop_back();
    }
    if(ans.size()>500)//把多于500的位干掉
        ans.resize(500);
    return ans;
}

bigint ksm(int p)//快速幂
{
    bigint base={2};
    bigint ans={1};
    while(p)
    {
        if(p&1)
            ans=ans*base;
        base=base*base;
        p>>=1;
    }
    ans.resize(500,0);//最后将ans缩到500位并补前导0
    return ans;
}

void print(bigint a)
{
    a[0]--;
    reverse(a.begin(),a.end());
    int j=1;
    for(auto i:a)//c++11 新特性
    {
        printf("%d",i);
        if(j%50==0)//分行输出
            printf("\n");
        j++;
    }
    return;
}

int main()
{
    int p;
    scanf("%d",&p);
    printf("%lld\n",(long long)(p*(double)log10((double)2.0)+1));//搞位数
    bigint ans=ksm(p);
    print(ans);
    return 0;
}
最后修改日期:2020年2月16日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。