QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#584624 | #7811. 一元二次方程 | MrPython | 100 ✓ | 5ms | 3720kb | C++14 | 4.2kb | 2024-09-23 15:52:52 | 2024-09-23 15:52:52 |
Judging History
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;
}
詳細信息
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