UOJ Logo

NOI.AC

2^a+2^b Problem题解

2024-10-11 21:03:17 By sycwhx

本题看似简单,直接输出$(1LL\lt\lt a+1LL\lt\lt b)$
但观察数据发现,$2^{63}+2^{63}=2^{64}$,而 long long 的最大值是 $2^{63}-1$ ,显然无法存下,即使使用 unsigned long long ,即$2^{64}-1$,也无济于事,因此,本题需要使用 __int128
__int128 是占用 $128$ 字节的整数存储类型,其范围是$-2^{127}$~$2^{127}-1$,在一定程度上可以取代高精度,实现起来也较高精度简单一些

当然,你也可以使用高精度解决,但就本题来说,使用 __int128 更为简单

需要注意,__int128 较普通的整数存储类型不同,不能直接使用cin/coutscanf/printf输入输出,因此需要写函数读入
下面给出基础的读入,在别的题中使用时要注意判断负数及其他特殊情况(如果你想了解更多可以见实验舱2699题快速选择(链接),题面给出了快读模版)

__int128 read()
{
    string str;
    cin>>str;
    __int128 res;
    for(int i=0;i<str.size();i++)
        res=res*10+str[i]-'0';
    return res;
}

剩下就是输出部分了,上文已经说过, __int128 无法使用输入输出,因此下面也给出递归输出模版:

void print(__int128 x)
{
    if(x==0)
        return;
    print(x/10)
    cout<<char(x%10+'0')//注意,即使是一位数 __int128 同样无法输出,因此需要强转char
}

有了 __int128 这样的工具,本题也不再困难,只需求出 $2^a$ 和 $2^b$ ,最后输出它们的和即可

AC代码:

#include<bits/stdc++.h>
using namespace std;
__int128 a,b,A=1,B=1;

__int128 read(){
    string str;
    cin>>str;
    __int128 res=0;
    for(int i=0;i<str.size();i++)
        res=res*10+(str[i]-'0');//秦九韶算法,逐位读入
    return res;
}

void print(__int128 x){
    if(x==0)
        return;
    print(x/10);
    cout<<char(x%10+'0');
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
    freopen("../data.out", "w", stdout);
#endif

    //使用函数读入数据
    a=read();
    b=read();
    for(int i=1;i<=a;i++)
        A*=2;
    for(int i=1;i<=b;i++)
        B*=2;
    print(A+B);//__int128数据用函数输出
    return 0;
}

评论

gfytre5yh
666
sycwhx
@gfytre5yh

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。