int和longlong运算出错


0


题目链接 蓝桥杯2021年第十二届国赛真题-123

显而易见，二分范围在int内，但如果把二分模板中的l,r,mid从long long改为int就会出错。
我感觉是int和longlong运算出的错，但是也只是感觉，真是莫名其妙的。

错误的代码：

#include<iostream>
using namespace std;

long long sum(long long x)
{
    if(x == 0) return 0;
    int l = 1,r = 2e6;  //改longlong
    while(l < r)
    {
        int mid = l + r + 1 >> 1;   //改longlong
        if(x >= mid * (mid + 1) / 2) l = mid;
        else r = mid - 1;
    }

    long long a = l * (l + 1) / 2 * (l + 1) - l * (l + 1) * (2 * l + 1) / 6;
    x -= l * (l + 1) / 2;
    a += x * (x + 1) / 2;
    return a;
}

int main()
{
    int t = 0;
    scanf("%d",&t);
    while(t--)
    {
        long long l = 0,r = 0;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",sum(r) - sum(l - 1));
    }
    return 0;
}


提问于21天前
21980


3 个问答


0

哦哦，我刚看懂你的代码。。那错的是这里if(x >= mid * (mid + 1) / 2)。mid*mid会爆int。

#include<iostream>
using namespace std;

typedef long long LL;

long long sum(long long x)
{
    if(x == 0) return 0;
    int l = 1,r = 2e6;  //改longlong
    while(l < r)
    {
        int mid = l + r + 1 >> 1;   //改longlong
        if(x >= (LL)mid * (mid + 1) / 2) l = mid;
        else r = mid - 1;
    }

    long long a = (LL)l * (l + 1) / 2 * (l + 1) - (LL)l * (l + 1) * (2 * l + 1) / 6;
    x -= (LL)l * (l + 1) / 2;
    a += x * (x + 1) / 2;
    return a;
}

int main()
{
    int t = 0;
    scanf("%d",&t);
    while(t--)
    {
        long long l = 0,r = 0;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",sum(r) - sum(l - 1));
    }
    return 0;
}

这么改就可以过。

回答于19天前
13941
原来是这样 大佬太厉害了 orz –  自律   16天前

0 

【评测用例规模与约定】
对于 10% 的评测用例，1 ≤ T ≤ 30, 1 ≤ li ≤ ri ≤ 100。
对于 20% 的评测用例，1 ≤ T ≤ 100, 1 ≤ li ≤ ri ≤ 1000。
对于 40% 的评测用例，1 ≤ T ≤ 1000, 1 ≤ li ≤ ri ≤ 106。
对于 70% 的评测用例，1 ≤ T ≤ 10000, 1 ≤ li ≤ ri ≤ 109。
对于 80% 的评测用例，1 ≤ T ≤ 1000, 1 ≤ li ≤ ri ≤ 1012。
对于 90% 的评测用例，1 ≤ T ≤ 10000, 1 ≤ li ≤ ri ≤ 1012。
对于所有评测用例，1 ≤ T ≤ 100000, 1 ≤ li ≤ ri ≤ 1012。

l、r的极限值是1e12啊。。
T是1e6，但T是询问的数据组数

回答于20天前
13941
不是您想的那样的，的这个li和ri是指下标，与二分模板中的l，r意义不同。 在这个题目中，二分是为了找到当数列最大数，当最大数是x时，数列中数的个数小于等于li或ri。 结合题目性质，根据等差数列知 x * (x + 1)/2小于1e12（li，ri），x(x + 1) < 2e12，所以x最大值约等于（根号2）e6，范围取大一点，就取2e6了，x也就是二分范围，不是li，ri的范围。 –  自律   20天前

0

int mid = l + r + 1 >> 1;
这一句，int类型的l和r在执行l+r时可能会爆int

回答于20天前
13941
但是l和r最大是2e6，加起来最大是4e6，小于int的范围2147483647。 –  自律   20天前
我来回答