题目: P9748 一元二次方程 [CSP-J2023]

思路:

做了一个分数的结构体, 模拟分数的各种运算, 然后再模拟求解一元二次方程

遇到的困难:

在运行样例的过程中发现部分的结果是正确的, 但是有部分样例的输出会导致符号错误($q1$或结果$result$的绝对值是正确的, 但是符号不对)

错误代码(10pts):

#include <cmath>
#include <iostream>
#include <string>

using namespace std;

inline int gcd(int a, int b) {
  if (a % b == 0)
    return b;
  else
    return gcd(b, a % b);
}

inline int lcm(int a, int b) { return (a * b) / gcd(a, b); }

inline int max_subsq(int x) {
  for (int i = (int)floor(sqrt(x)); i >= 1; i--) {
    if (x % (i * i) == 0)
      return i;
  }
  return 1;
}

struct FracNum {
  bool sign_v;
  int top_num;
  int bot_num;
  FracNum(int t, int b, bool s) : top_num(t), bot_num(b), sign_v(s) {}
  void simplify() { // 化简分数
    if (top_num == 0) {
      this->bot_num = 1;
      this->sign_v = false;
      return;
    }
    bool sign_tp = this->top_num < 0;
    bool sign_bt = this->bot_num < 0;
    if (sign_tp & sign_bt) {
      this->top_num = -this->top_num;
      this->bot_num = -this->bot_num;
      // this->sign_v = false;
    } else if (sign_bt ^ sign_tp) {
      if (this->top_num < 0)
        this->top_num = -this->top_num;
      if (this->bot_num < 0)
        this->bot_num = -this->bot_num;
      this->sign_v = -this->sign_v;
    } else {
      // this->sign_v = false;
    }

    int gd = gcd(this->top_num, this->bot_num);
    if (gd == 1)
      return;
    else {
      this->top_num /= gd;
      this->bot_num /= gd;
    }
  }
  FracNum *operator*=(int x) {
    this->top_num *= x;
    return this;
  }
  FracNum *operator/=(int x) {
    this->bot_num *= x;
    return this;
  }
  FracNum operator*(int x) {
    return FracNum(this->top_num * x, this->bot_num, this->sign_v);
  }
  FracNum operator/(int x) {
    return FracNum(this->top_num, this->bot_num, this->sign_v);
  }
  FracNum operator+(FracNum b) {
    if (b.top_num == 0) {
      return *this;
    } else if (this->top_num == 0) {
      return b;
    } else if (this->sign_v ^ b.sign_v) { // 两者符号不一样
      if (this->sign_v) {                 // 这是负数
        int upnm = b.top_num * this->bot_num - this->top_num * b.bot_num;
        if (upnm < 0) {
          FracNum result(-upnm, this->bot_num * b.bot_num, true);
          result.simplify();
          return result;
        } else {
          FracNum result(upnm, this->bot_num * b.bot_num, false);
          result.simplify();
          return result;
        }
      } else { // B是负数
        int upnm = this->top_num * b.bot_num - b.top_num * this->bot_num;
        if (upnm < 0) {
          FracNum result(-upnm, this->bot_num * b.bot_num, true);
          result.simplify();
          return result;
        } else {
          FracNum result(upnm, this->bot_num * b.bot_num, false);
          result.simplify();
          return result;
        }
      }
    } else {
      FracNum result(this->top_num * b.bot_num + b.top_num * this->bot_num,
                     this->bot_num * b.bot_num, this->sign_v);
      result.simplify();
      return result;
    }
  }
  string convert() { // 转换为字符串
    if (this->bot_num == 1) {
      if (this->sign_v) {
        string bd = "-";
        bd += to_string(this->top_num);
        return bd;
      } else {
        return to_string(this->top_num);
      }
    } else {
      if (this->sign_v) {
        string bd = "-";
        bd += to_string(this->top_num);
        bd += '/';
        bd += to_string(this->bot_num);
        return bd;
      } else {
        string bd = "";
        bd += to_string(this->top_num);
        bd += "/";
        bd += to_string(this->bot_num);
        return bd;
      }
    }
  }
};

inline int get_delta(int a, int b, int c) { return (b * b) - 4 * a * c; }

inline string build_answer(int a, int b, int c) {
  if (get_delta(a, b, c) < 0)
    return "NO";
  string builder = "";
  FracNum q1(b, 2 * a, true);
  q1.simplify();

  int delta = get_delta(a, b, c);
  int extra_subnum = max_subsq(delta);
  delta /= extra_subnum * extra_subnum;

  FracNum q2_1(extra_subnum, 2 * a, false); // sqrt(delta) / 2a
  FracNum q2_2(extra_subnum, 2 * a, true);  // -sqrt(delta) / 2a

  q2_1.simplify();
  q2_2.simplify();

  if (delta == 0) {
    return q1.convert();
  } else if (delta == 1) {
    if (a < 0) {
      FracNum result(q1 + q2_2);
      result.simplify();
      return result.convert();
    } else {
      FracNum result(q1 + q2_1);
      result.simplify();
      return result.convert();
    }
  } else {
    if (b == 0) {

      if (q2_2.bot_num == 1 && q2_2.top_num == 1) {
        builder += "sqrt(";
        builder += to_string(delta);
        builder += ")";
        return builder;
      } else if (q2_2.bot_num == 1) {
        builder += to_string(q2_2.top_num);
        builder += "*sqrt(";
        builder += to_string(delta);
        builder += ")";
        return builder;
      } else if (q2_2.top_num == 1) {
        builder += "sqrt(";
        builder += to_string(delta);
        builder += ")/";
        builder += to_string(q2_2.bot_num);
        return builder;
      } else {
        builder += to_string(q2_2.top_num);
        builder += "*sqrt(";
        builder += to_string(delta);
        builder += ")/";
        builder += to_string(q2_2.bot_num);
        return builder;
      }
    } else {
      builder += q1.convert();
      builder += "+";
      if (q2_2.bot_num == 1 && q2_2.top_num == 1) {
        builder += "sqrt(";
        builder += to_string(delta);
        builder += ")";
        return builder;
      } else if (q2_2.bot_num == 1) {
        builder += to_string(q2_2.top_num);
        builder += "*sqrt(";
        builder += to_string(delta);
        builder += ")";
        return builder;
      } else if (q2_2.top_num == 1) {
        builder += "sqrt(";
        builder += to_string(delta);
        builder += ")/";
        builder += to_string(q2_2.bot_num);
        return builder;
      } else {
        builder += to_string(q2_2.top_num);
        builder += "*sqrt(";
        builder += to_string(delta);
        builder += ")/";
        builder += to_string(q2_2.bot_num);
        return builder;
      }
      return builder;
    }
  }
}

int main() {
  int T, M;
  scanf("%d %d", &T, &M);
  for (int i = 1; i <= T; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    cout << build_answer(a, b, c) << endl;
  }
  return 0;
}

样例 & 期望输出 & 实际输出

样例输入:

9 1000
1 -1 0
-1 -1 -1
1 -2 1
1 5 4
4 4 1
1 0 -432
1 -3 1
2 -4 1
1 7 1

样例输出:

1
NO
1
-1
-1/2
12*sqrt(3)
3/2+sqrt(5)/2
1+sqrt(2)/2
-7/2+3*sqrt(5)/2

实际输出(已用<-ERROR标出不同处):

0
NO
-1 <-ERROR!
-1
-1/2
12*sqrt(3)
-3/2+sqrt(5)/2 <-ERROR!
-1+sqrt(2)/2 <-ERROR!
-7/2+3*sqrt(5)/2

十分感谢!