蓝桥杯国赛问题123找BUG找了好久

Question

//该代码通过率只有70%，因为大数的缘故卡了，原因不知道；

#include <iostream>
#include<cmath>
using namespace std;
long long T ;
long long n1,n2;
long long L,R;
long long f(long long n,long long m)
{
return round(1.0*(n-m)*(n*n+n*m+m*m)/6+1.0*(n-m)*(n+m)/2+1.0*(n-m)/3);
}
long long find(long long x)
{long long low=0,high=x+1;
  while(low+1<high)
  {
    long long mid=(low+high)/2;
    if(mid*(mid+1)<=x)
         low=mid;
    else
    high=mid;
  }
  if(low*(low+1)==x)
  return low;
  else
  return low+1;
}
int main()
{
  scanf("%lld",&T);
  while(T--)
  {
    scanf("%lld%lld",&L,&R);
    n1=find(2*L);
    n2=find(2*R);
   // cout<<"{"<<n1<<" "<<n2<<"}"<<endl;
    long long ans1=L-n1*(n1-1)/2;
    long long ans2=R-n2*(n2-1)/2;
   //cout<<ans1<<" "<<ans2<<endl;
    long long ans=f(n2,n1-1);
    //cout<<"{}"<<f(n2,n1-1)<<endl;
    ans-=(ans1-1)*ans1/2;
    ans-=(n2-ans2)*(ans2+1+n2)/2;
    printf("%lld\n",ans);

  }
  return 0;
}

Answer 1

该回答引用自GPT-3.5,由博主GIS_Liu编写：

首先，分析这段代码的逻辑和问题所在：

1. 代码逻辑：该代码是一个循环结构，每次循环中输入两个整数 L 和 R，然后通过一系列计算求解并输出一个结果。具体来说，它首先通过 find 函数找到满足条件的整数 n1 和 n2，然后计算 ans1 和 ans2，接着调用函数 f 计算 ans，最后根据一定的规则对 ans 进行一系列减法运算，并输出结果。

2. 问题分析：

   • 问题一：该代码只能通过 70% 的测试用例，因为在处理大数时出现了问题，导致结果不正确。
   • 问题二：具体原因在于对大数的处理不够准确，可能存在数据溢出或者精度丢失的情况。

基于以上分析，下面是解决思路与解决方案：

1. 处理大数问题：

   • 在计算过程中，可能会出现整数溢出或精度丢失的情况，特别是涉及到大整数的运算时。为了解决这个问题，可以使用支持大数运算的库，如 C++ 中的 boost::multiprecision 或者 long long 类型（64 位整数）。

2. 代码修改：

   • 将涉及到大数运算的部分，如乘法、除法等，替换成对应的支持大数运算的函数或数据类型。
   • 在计算过程中，尽量避免中间结果的溢出或精度丢失，可以通过分解运算、增加数据类型的位数等方式来解决。

下面是修改后的代码：

#include <iostream>
#include <cmath>
#include <boost/multiprecision/cpp_int.hpp> // 引入boost库进行大数运算
using namespace std;
using namespace boost::multiprecision;

cpp_int T;
cpp_int n1, n2;
cpp_int L, R;

cpp_int f(cpp_int n, cpp_int m) {
    return round(1.0 * (n - m) * (n * n + n * m + m * m) / 6 + 1.0 * (n - m) * (n + m) / 2 + 1.0 * (n - m) / 3);
}

cpp_int find(cpp_int x) {
    cpp_int low = 0, high = x + 1;
    while (low + 1 < high) {
        cpp_int mid = (low + high) / 2;
        if (mid * (mid + 1) <= x)
            low = mid;
        else
            high = mid;
    }
    if (low * (low + 1) == x)
        return low;
    else
        return low + 1;
}

int main() {
    cin >> T;
    while (T--) {
        cin >> L >> R;
        n1 = find(2 * L);
        n2 = find(2 * R);
        cpp_int ans1 = L - n1 * (n1 - 1) / 2;
        cpp_int ans2 = R - n2 * (n2 - 1) / 2;
        cpp_int ans = f(n2, n1 - 1);
        ans -= (ans1 - 1) * ans1 / 2;
        ans -= (n2 - ans2) * (ans2 + 1 + n2) / 2;
        cout << ans << endl;
    }
    return 0;
}

这样修改后的代码应该能够正确处理大数，提高通过率。

如果该回答解决了您的问题，请采纳！如果没有，请详述问题所在！