1065 A+B and C (64bit) (20分)

PAT上有个错误数据是错的,PAT上说明数据范围是([-2^{63}, 2^{63}]),但这个区间里一共有 (2^{64} + 1) 个数,已经超出了64bit的范围。

AcWing上将范围限制到了 ([-2^{63}, 2^{63} - 1])

由于long long的范围是([-2^{63},2^{63})),因此题目中给出的两个整数相加有可能会溢出(正溢出或负溢出),直接进行大小判断会造成错误。在计算机组成原理中会指出,如果两个正数之和等于负数或是两个负数之和等于正数,那么就是溢出。对于溢出后的具体范围,可以进行如下分析:

  1. (A+B ge 2^{63}) 时,显然有A+B>C成立,但A+B会因超过long long的正向最大值而发生正溢出。由于题目给定的A和B最大均为(2^{63}-1),故A+B最大为(2^{64}-2),因此使用long long存储正溢出后的值的区间为([-2^{63}, -2])(由((2^{64}-2) \% (2^{64})=-2)可得右边界)。所以,当A>0,B>0,A+B<0时为正溢出,输出true。

  2. (A+B<-2^{63}) 时,显然有A+B<C成立,但A+B会因超过long long的负向最小值而发生负溢出。由于题目给定的A和B最小均为(-2^{63}),故A+B最小为(-2^{64}),因此使用long long存储负溢出后的值的区间为([0,2^{63}))(由((-2^{64}) %2^{64}=0)可得左边界)。所以,当A<0,B<
    0,A+B≥0时为负溢出,输出false。

  3. 在没有溢出的情况下,当A+B>C时,输出true;当A+B≤C时,输出false。

LL a,b,c;
int n;

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cout<<"Case #"<<i<<": ";
        scanf("%lld%lld%lld",&a,&b,&c);
        LL sum=a+b;
        if(a>0 && b>0 && sum<0) //上溢
            cout<<"true"<<endl;
        else if(a<0 && b<0 && sum>=0) //下溢
            cout<<"false"<<endl;
        else if(sum>c)
            cout<<"true"<<endl;
        else
            cout<<"false"<<endl;
    }

    //system("pause");
    return 0;
}
原文地址:https://www.cnblogs.com/fxh0707/p/14250817.html