QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#584624#7811. 一元二次方程MrPython100 ✓5ms3720kbC++144.2kb2024-09-23 15:52:522024-09-23 15:52:52

Judging History

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

  • [2024-09-23 15:52:52]
  • 评测
  • 测评结果:100
  • 用时:5ms
  • 内存:3720kb
  • [2024-09-23 15:52:52]
  • 提交

answer

#include <bits/extc++.h>
using namespace std;
namespace pbds = __gnu_pbds;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
ui constexpr prime[] = {
    2,    3,    5,    7,    11,   13,   17,   19,   23,   29,   31,   37,
    41,   43,   47,   53,   59,   61,   67,   71,   73,   79,   83,   89,
    97,   101,  103,  107,  109,  113,  127,  131,  137,  139,  149,  151,
    157,  163,  167,  173,  179,  181,  191,  193,  197,  199,  211,  223,
    227,  229,  233,  239,  241,  251,  257,  263,  269,  271,  277,  281,
    283,  293,  307,  311,  313,  317,  331,  337,  347,  349,  353,  359,
    367,  373,  379,  383,  389,  397,  401,  409,  419,  421,  431,  433,
    439,  443,  449,  457,  461,  463,  467,  479,  487,  491,  499,  503,
    509,  521,  523,  541,  547,  557,  563,  569,  571,  577,  587,  593,
    599,  601,  607,  613,  617,  619,  631,  641,  643,  647,  653,  659,
    661,  673,  677,  683,  691,  701,  709,  719,  727,  733,  739,  743,
    751,  757,  761,  769,  773,  787,  797,  809,  811,  821,  823,  827,
    829,  839,  853,  857,  859,  863,  877,  881,  883,  887,  907,  911,
    919,  929,  937,  941,  947,  953,  967,  971,  977,  983,  991,  997,
    1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
    1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
    1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249,
    1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
    1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439,
    1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
    1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601,
    1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
    1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783,
    1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
    1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
    1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069,
    2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143,
    2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,
    2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347,
    2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
    2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543,
    2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657,
    2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713,
    2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,
    2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
    2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999};
int main(void) {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  size_t T;
  int M;
  cin >> T >> M;
  while (T--) {
    int a, b, c;
    cin >> a >> b >> c;
    int delta = b * b - 4 * a * c;
    if (delta < 0) {
      cout << "NO\n";
      continue;
    }
    if (int(sqrt(delta)) * int(sqrt(delta)) == delta) {
      int fz = -b + int(a > 0 ? sqrt(delta) : -sqrt(delta)), fm = 2 * a;
      int gcd = __gcd(fz, fm);
      fz /= gcd, fm /= gcd;
      if (fm < 0) fm *= -1, fz *= -1;
      cout << fz;
      if (fm != 1) cout << '/' << fm;
      cout.put('\n');
    } else {
      int fza = -b, fma = 2 * a;
      int gcda = __gcd(fza, fma);
      fza /= gcda, fma /= gcda;
      if (fma < 0) fma *= -1, fza *= -1;
      int fzb = (a > 0 ? 1 : -1), fmb = 2 * a, sqt = delta;
      for (ui i : prime)
        while (!(sqt % (i * i))) sqt /= i * i, fzb *= i;
      int gcdb = __gcd(fzb, fmb);
      fzb /= gcdb, fmb /= gcdb;
      if (fmb < 0) fmb *= -1, fzb *= -1;
      if (fza) {
        cout << fza;
        if (fma != 1) cout << '/' << fma;
        if (fzb > 0) cout.put('+');
      }
      if (fzb == -1)
        cout.put('-');
      else if (fzb != 1)
        cout << fzb << '*';
      cout << "sqrt(" << sqt << ')';
      if (fmb != 1) cout << '/' << fmb;
      cout << '\n';
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

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

input:

2 1
-1 0 0
1 0 0

output:

0
0

result:

ok 2 lines

Test #2:

score: 10
Accepted
time: 5ms
memory: 3516kb

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: 3652kb

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: 3ms
memory: 3676kb

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: 1ms
memory: 3580kb

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: 1ms
memory: 3648kb

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: 1ms
memory: 3648kb

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: 1ms
memory: 3584kb

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: 4ms
memory: 3720kb

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: 3ms
memory: 3624kb

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