QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#603877#7811. 一元二次方程tiankonguse100 ✓4ms3940kbC++202.2kb2024-10-01 20:32:382024-10-01 20:32:40

Judging History

你现在查看的是最新测评结果

  • [2024-10-01 20:32:40]
  • 评测
  • 测评结果:100
  • 用时:4ms
  • 内存:3940kb
  • [2024-10-01 20:32:38]
  • 提交

answer

/*
ID: tiankonguse
TASK: uqe
LANG: C++
CONTEST: CSP-J 2023
OJ: https://qoj.ac/contest/1427/problem/7811
*/
#define TASK "uqe"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void InitIO() {
  // #ifndef USACO_LOCAL_JUDGE
  //   freopen(TASK ".in", "r", stdin);
  //   freopen(TASK ".out", "w", stdout);
  // #endif
}

/*
 */

// 朴素 GCD/gcd 算法,复杂度 Log(n))
ll Gcd(ll x, ll y) {
  if (!x || !y) return x ? x : y;
  for (ll t; t = x % y; x = y, y = t);
  return y;
}

ll a, b, c;
void Fix() {
  ll k = abs(Gcd(Gcd(a, b), c));
  if (a < 0) {
    k = -k;
  }
  a /= k;
  b /= k;
  c /= k;
}
void output(ll p, ll q) {
  ll k = abs(gcd(p, q));
  p /= k;
  q /= k;
  if (q == 1) {
    printf("%lld", p);
  } else {
    printf("%lld/%lld", p, q);
  }
}
ll sqrFactor(ll sq, ll d) {
  for (ll i = sq; i >= 1; i--) {
    if (d % (i * i) == 0) {
      return i;
    }
  }
  return 1;
}
void RealSolver() {
  Fix();

  ll d = b * b - 4 * a * c;
  // printf("a=%lld b=%lld c=%lld d=%lld\n", a, b, c, d);

  if (d < 0) {  // 无解
    printf("NO\n");
    return;
  }

  if (d == 0) {
    output(-b, 2 * a);  // 一个解
    printf("\n");
    return;
  }

  // 有两个解
  ll sq = sqrt(d);
  if (sq * sq == d) {        // 有理数解
    output(-b + sq, 2 * a);  // 一个解
    printf("\n");
    return;
  }

  if (b != 0) {
    output(-b, 2 * a);
    printf("+");
  }
  ll p = sqrFactor(sq, d);
  ll q = 2 * a;
  d /= p * p;
  ll k = abs(gcd(p, q));
  p /= k;
  q /= k;
  if (p == 1 && q == 1) {
    printf("sqrt(%lld)\n", d);
  } else if (p > 1 && q == 1) {
    printf("%lld*sqrt(%lld)\n", p, d);
  } else if (p == 1 && q > 1) {
    printf("sqrt(%lld)/%lld\n", d, q);
  } else {
    printf("%d*sqrt(%lld)/%lld\n", p, d, q);
  }
}
void Solver() {  //
  ll t, m;
  scanf("%lld%lld", &t, &m);
  while (t--) {
    scanf("%lld%lld%lld", &a, &b, &c);
    RealSolver();
  }
}

int main() {
  InitIO();
  Solver();
  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
*/

詳細信息


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 3788kb

input:

2 1
-1 0 0
1 0 0

output:

0
0

result:

ok 2 lines

Test #2:

score: 10
Accepted
time: 2ms
memory: 3940kb

input:

4838 20
1 -19 5
-2 12 15
1 8 7
1 8 -8
-1 -11 0
-1 -7 -7
-2 -5 8
2 -8 -13
-1 -10 11
-1 -15 0
1 -5 18
-2 -9 13
-1 20 17
1 -17 -3
1 0 1
-2 -4 -2
2 -11 10
1 -2 -1
1 11 -18
-1 11 0
-1 4 16
1 18 3
-2 -3 6
-2 -14 -11
1 -12 12
2 -13 -9
1 -9 -12
1 16 -2
-2 -9 2
2 -2 -1
1 3 -6
-2 11 4
-1 -11 4
-1 13 0
-1 -4 1...

output:

19/2+sqrt(341)/2
3+sqrt(66)/2
-1
-4+2*sqrt(6)
0
-7/2+sqrt(21)/2
-5/4+sqrt(89)/4
2+sqrt(42)/2
1
0
NO
-9/4+sqrt(185)/4
10+3*sqrt(13)
17/2+sqrt(301)/2
NO
-1
11/4+sqrt(41)/4
1+sqrt(2)
-11/2+sqrt(193)/2
11
2+2*sqrt(5)
-9+sqrt(78)
-3/4+sqrt(57)/4
-7/2+3*sqrt(3)/2
6+2*sqrt(6)
13/4+sqrt(241)/4
9/2+sqrt(129)...

result:

ok 4838 lines

Test #3:

score: 10
Accepted
time: 1ms
memory: 3860kb

input:

4802 1000
86 0 774
203 0 -203
3 0 27
420 0 -420
-256 0 256
-532 0 0
-493 0 -493
664 0 0
51 0 -204
-21 0 -21
223 0 0
-332 0 332
371 0 -371
799 0 0
-544 0 0
-749 0 -749
-26 0 650
-43 0 387
-460 0 -460
21 0 -525
298 0 0
-66 0 66
28 0 700
82 0 -738
109 0 436
207 0 -207
336 0 0
-136 0 -544
-50 0 450
82 0...

output:

NO
1
NO
1
1
0
NO
0
2
NO
0
1
1
0
0
NO
5
3
NO
5
0
1
NO
3
NO
1
0
NO
3
NO
8
2
0
NO
0
NO
NO
1
1
0
0
NO
1
0
NO
0
NO
NO
0
NO
0
1
NO
0
NO
0
0
1
2
2
3
NO
NO
NO
0
NO
1
NO
0
11
1
0
1
2
NO
0
0
NO
NO
0
NO
0
0
NO
0
0
NO
NO
0
8
1
0
1
2
NO
NO
0
NO
NO
0
2
4
2
0
NO
NO
1
3
NO
1
2
NO
NO
NO
NO
0
NO
2
1
1
0
NO
NO
0
4
NO
...

result:

ok 4802 lines

Test #4:

score: 10
Accepted
time: 4ms
memory: 3852kb

input:

4084 1000
-413 0 -760
56 0 472
338 0 868
446 0 -769
-268 0 -2
7 0 247
-53 0 593
415 0 284
138 0 983
-357 0 -539
-179 0 -47
414 0 154
-226 0 -963
440 0 -418
-212 0 877
-201 0 -846
300 0 -594
-135 0 -375
204 0 548
265 0 -173
-412 0 717
231 0 -642
-71 0 -260
489 0 469
-305 0 -958
352 0 244
-239 0 86
10...

output:

NO
NO
NO
sqrt(342974)/446
NO
NO
sqrt(31429)/53
NO
NO
NO
NO
NO
NO
sqrt(95)/10
sqrt(46481)/106
NO
3*sqrt(22)/10
NO
NO
sqrt(45845)/265
sqrt(73851)/206
sqrt(16478)/77
NO
NO
NO
NO
sqrt(20554)/239
sqrt(70490)/106
NO
NO
sqrt(201815)/223
NO
NO
sqrt(1938)/38
sqrt(2146)/37
3*sqrt(3311)/77
NO
NO
sqrt(182)/13
N...

result:

ok 4084 lines

Test #5:

score: 10
Accepted
time: 0ms
memory: 3784kb

input:

5000 1000
12 -564 0
158 632 0
7 658 0
-16 832 0
487 -487 0
430 430 0
-2 412 0
-59 -472 0
284 -852 0
-455 -910 0
-29 29 0
-2 760 0
81 -243 0
5 -360 0
-145 435 0
247 -988 0
-61 -244 0
4 -520 0
-9 -927 0
10 -900 0
-307 0 0
-1 692 0
1 787 0
42 378 0
11 -704 0
-1 392 0
1 -537 0
3 567 0
-86 -860 0
192 768...

output:

47
0
0
52
1
0
206
0
3
0
1
380
3
72
3
4
0
130
0
90
0
692
0
0
64
392
537
0
0
0
0
0
1
1
0
0
11
609
133
146
0
0
0
0
0
80
0
0
0
20
0
0
0
0
682
3
0
0
0
114
9
1
103
0
385
0
0
0
0
9
0
0
3
0
6
0
0
0
0
60
0
0
2
0
0
0
0
0
663
0
65
183
56
60
0
28
0
489
671
51
12
0
25
0
0
0
8
2
0
2
6
3
0
14
0
0
0
0
0
12
0
0
0
0
...

result:

ok 5000 lines

Test #6:

score: 10
Accepted
time: 2ms
memory: 3868kb

input:

5000 1000
391 -246 0
435 908 0
-395 555 0
18 -412 0
-40 -24 0
-49 -510 0
297 -440 0
-484 -122 0
-205 -603 0
440 434 0
-423 103 0
-121 657 0
109 818 0
426 -401 0
201 -937 0
77 923 0
98 785 0
-74 524 0
-168 -52 0
417 -224 0
385 100 0
37 -762 0
-346 573 0
-147 68 0
-275 359 0
-59 966 0
115 340 0
159 -3...

output:

246/391
0
111/79
206/9
0
0
40/27
0
0
0
103/423
657/121
0
401/426
937/201
0
0
262/37
0
224/417
0
762/37
573/346
68/147
359/275
966/59
0
365/159
0
652/181
0
954/113
0
732/107
815/243
509/279
0
0
0
403/23
0
68/79
0
0
0
0
0
0
0
819/11
0
241/140
40/13
0
0
0
0
0
553/298
0
219/412
0
823/256
14/3
0
444/343
...

result:

ok 5000 lines

Test #7:

score: 10
Accepted
time: 2ms
memory: 3856kb

input:

5000 1000
-2 -328 330
-7 -987 0
6 -72 -510
-3 6 504
-9 837 0
-3 489 0
-10 -760 -750
-3 471 -468
1 57 -118
4 -120 644
6 -18 -648
-1 31 32
-2 -48 -88
1 -1 7
6 162 156
-4 108 -704
1 -8 -209
7 154 -525
2 430 428
1 -44 448
-3 -51 -126
7 -420 -868
1 -189 920
1 40 375
-1 80 -231
-4 -76 864
-1 -33 -90
1 -39...

output:

1
0
17
14
93
163
-1
156
2
23
12
32
-2
NO
-1
16
19
3
-1
28
-3
62
184
-15
77
8
-3
31
10
-1
20
122
1
0
160
2
28
0
0
1
3
314
-3
1
-1
0
40
0
-20
10
40
85
24
NO
109
233
1
-2
-20
NO
11
41
33
57
84
1
-1
NO
41
60
28
-6
112
232
84
0
45
68
1
639
20
9
-2
1
-2
192
-1
86
6
-2
0
3
38
14
314
53
33
18
101
13
86
-1
-...

result:

ok 5000 lines

Test #8:

score: 10
Accepted
time: 2ms
memory: 3752kb

input:

5000 1000
8 -352 -736
-1 -10 264
7 119 420
-4 188 -528
-8 -616 624
-1 609 610
1 881 880
7 588 581
-2 254 780
1 85 -546
-8 -248 -240
2 -718 -720
-3 123 -930
-5 -425 430
1 -104 -212
6 -168 162
1 105 950
-6 -510 0
-9 -423 -414
1 -313 0
-5 -750 0
2 -652 650
2 -270 532
-1 85 450
-3 57 870
-1 -804 -803
1 ...

output:

46
12
-5
44
1
610
-1
-1
130
6
-1
360
31
1
106
27
-10
0
-1
313
0
325
133
90
29
-1
321
114
420
3
-2
-1
-5
5
74
66
131
-1
289
210
67
-5
5
9
-1
-2
1
207
18
181
1
0
0
5
60
177
12
10
-2
12
-11
1
2
-2
-8
0
-1
-9
14
76
3
5
NO
11
-8
8
-4
0
26
11
65
64
-3
49
44
120
165
0
50
384
246
38
464
90
65
19
66
12
58
-2...

result:

ok 5000 lines

Test #9:

score: 10
Accepted
time: 2ms
memory: 3760kb

input:

5000 1000
-4 48 48
-10 -140 -540
16 96 104
-6 -60 -150
-2 -1 -5
-5 -20 -20
81 -324 144
-6 84 -780
256 -768 -624
144 576 -153
400 600 -287
1 -4 102
-4 -24 -36
36 -72 32
9 -180 868
-7 14 -903
5 -90 450
400 320 -236
8 -32 40
5 -80 480
-6 -12 372
9 18 -15
6 -60 366
3 -6 963
1 -12 -160
-7 0 0
-1 -14 441
...

output:

6+4*sqrt(3)
NO
-3+sqrt(10)/2
-5
NO
-2
2+2*sqrt(5)/3
NO
3/2+5*sqrt(3)/4
1/4
-3/4+4*sqrt(2)/5
NO
-3
4/3
10+4*sqrt(2)/3
NO
NO
-2/5+sqrt(3)/2
NO
NO
-1+3*sqrt(7)
-1+2*sqrt(6)/3
NO
NO
20
0
-7+7*sqrt(10)
NO
NO
1+4*sqrt(3)
3/2
2
NO
NO
NO
8+sqrt(5)
-9+5*sqrt(7)
1+6*sqrt(2)
12
10+4*sqrt(3)
NO
11
NO
5
9/2
NO
1...

result:

ok 5000 lines

Test #10:

score: 10
Accepted
time: 0ms
memory: 3868kb

input:

5000 1000
225 150 -299
-2 16 -8
4 8 -252
4 -24 -540
5 10 -3
2 20 -538
4 48 -144
4 16 -11
-4 -24 828
3 60 84
4 9 5
8 -64 -264
-5 -80 940
-8 -128 64
6 -12 582
25 30 -16
36 -180 -927
-10 60 160
-3 3 -10
6 -108 -474
25 -250 282
9 144 495
4 -80 144
1 -14 54
-5 -60 -175
4 -40 52
16 -160 240
1 -16 145
36 -...

output:

13/15
4+2*sqrt(3)
7
15
-1+2*sqrt(10)/5
-5+7*sqrt(6)
-6+6*sqrt(2)
-2+3*sqrt(3)/2
-3+6*sqrt(6)
-10+6*sqrt(2)
-1
11
-8+6*sqrt(7)
-8+6*sqrt(2)
NO
2/5
5/2+4*sqrt(2)
8
NO
9+4*sqrt(10)
5+7*sqrt(7)/5
-5
18
NO
-5
5+2*sqrt(3)
5+sqrt(10)
NO
23/6
-5/8+sqrt(57)/8
-1+3*sqrt(6)
-3
6+7*sqrt(3)
9+5*sqrt(5)/3
NO
NO
-...

result:

ok 5000 lines