P9750 [CSP-J 2023] 一元二次方程 题解

Mights · 2023-10-27 14:24:06 · 个人记录

P9750 [CSP-J 2023] 一元二次方程

题面：对于一元二次方程 ax^2+bx+c=0

• 如果 \Delta < 0 输出 NO

• 否则按照题面给你的格式输出两个解中较大的

解析

我们首先可以封装一个输出 p \div q 的函数，注意如果我们穿进去的参数为 x, y 则

• 求出最大公约数，保证 p \ ⊥ \ q

• 如果 y<0，则 x=-x, \ y=-y （保证 y 非负）

• 输出 x

• 如果 y \neq 1，输出 y

那代码应该很好写了......

void frac(int x, int y)
{
  int g = __gcd(x, y);
  x /= g, y /= g;
  if (y < 0)
    x = -x, y = -y;
  printf("%d", x);
  if (y != 1)
    printf("/%d", y);
}

接下来输入

接下来这一步很关键！！！

如果 a<0，则 a=-a, \ b=-b, \ c=-c （保证 a 非负）

接下来计算 \Delta

• 判断 \Delta < 0，输出 NO 并结束

• 如果 \Delta = 0，应该输出 \frac{-b}{2a}

• 否则计算 s=\sqrt\Delta

  • 如果 s \times s = \Delta，输出 \frac{s-b}{2a}，结束此询问

  • 按照格式，如果 b \neq 0，输出 \frac{-b}{2a}，并再来一个 + 号（即为题目中的 q_1）

  • 令 \Delta=\prod_{i=1}^{k}{p_i^{c_i}}，其中 p_i 为质数，c_i \neq 0，且 \forall i \in [1,k) 满足 p_i < p_{i+1}，则记 q=\prod_{i=1}^{k}p_i^{\lfloor \frac{c_i}{2} \rfloor}，则 q 即为题目中的 q_2，\frac{\Delta}{q^2} 即为题目中的 d

    代码如下：

    for (int i = 2; i <= s; i++)
    while (delta % (i * i) == 0)
      delta /= i * i, q *= i;

  • 注意，在这里我们仍然要求 \text{gcd}(q, 2a)

  • 输出

    • 如果 q \neq 1，输出 q 并再来一个 * 号

    • 输出 \text{sqrt}(\frac{\Delta}{q^2})

    • 输出 /{2a}

    代码如下：

    int g = abs(__gcd(q, y));
    q /= g, y /= g;
    if (q != 1)
    printf("%d*", q);
    printf("sqrt(%d)", delta);
    if (y != 1)
    printf("/%d", y);
    puts("");

注

题解中所有给出的形如 x_1 \ ⊥ \ x_2 的形式，表示 x_1 与 x_2 互质