T3在洛谷能AC,但是在小图灵和云斗都只拿到了80分,故在此处求hack,悬赏同学的(@mujinhao)关注。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
inline ll read() {
char c = 0;
ll x = 0;
bool f = 0;
while (c < '0' || c > '9') f |= (c=='-'), c = getchar();
while ('0' <= c && c <= '9') x = x*10+(c-'0'), c = getchar();
return f?-x:x;
}
int simpn2[168][2] = {{4, 2}, {9, 3}, {25, 5}, {49, 7}, {121, 11}, {169, 13}, {289, 17}, {361, 19}, {529, 23}, {841, 29}, {961, 31}, {1369, 37}, {1681, 41}, {1849, 43}, {2209, 47}, {2809, 53}, {3481, 59}, {3721, 61}, {4489, 67}, {5041, 71}, {5329, 73}, {6241, 79}, {6889, 83}, {7921, 89}, {9409, 97}, {10201, 101}, {10609, 103}, {11449, 107}, {11881, 109}, {12769, 113}, {16129, 127}, {17161, 131}, {18769, 137}, {19321, 139}, {22201, 149}, {22801, 151}, {24649, 157}, {26569, 163}, {27889, 167}, {29929, 173}, {32041, 179}, {32761, 181}, {36481, 191}, {37249, 193}, {38809, 197}, {39601, 199}, {44521, 211}, {49729, 223}, {51529, 227}, {52441, 229}, {54289, 233}, {57121, 239}, {58081, 241}, {63001, 251}, {66049, 257}, {69169, 263}, {72361, 269}, {73441, 271}, {76729, 277}, {78961, 281}, {80089, 283}, {85849, 293}, {94249, 307}, {96721, 311}, {97969, 313}, {100489, 317}, {109561, 331}, {113569, 337}, {120409, 347}, {121801, 349}, {124609, 353}, {128881, 359}, {134689, 367}, {139129, 373}, {143641, 379}, {146689, 383}, {151321, 389}, {157609, 397}, {160801, 401}, {167281, 409}, {175561, 419}, {177241, 421}, {185761, 431}, {187489, 433}, {192721, 439}, {196249, 443}, {201601, 449}, {208849, 457}, {212521, 461}, {214369, 463}, {218089, 467}, {229441, 479}, {237169, 487}, {241081, 491}, {249001, 499}, {253009, 503}, {259081, 509}, {271441, 521}, {273529, 523}, {292681, 541}, {299209, 547}, {310249, 557}, {316969, 563}, {323761, 569}, {326041, 571}, {332929, 577}, {344569, 587}, {351649, 593}, {358801, 599}, {361201, 601}, {368449, 607}, {375769, 613}, {380689, 617}, {383161, 619}, {398161, 631}, {410881, 641}, {413449, 643}, {418609, 647}, {426409, 653}, {434281, 659}, {436921, 661}, {452929, 673}, {458329, 677}, {466489, 683}, {477481, 691}, {491401, 701}, {502681, 709}, {516961, 719}, {528529, 727}, {537289, 733}, {546121, 739}, {552049, 743}, {564001, 751}, {573049, 757}, {579121, 761}, {591361, 769}, {597529, 773}, {619369, 787}, {635209, 797}, {654481, 809}, {657721, 811}, {674041, 821}, {677329, 823}, {683929, 827}, {687241, 829}, {703921, 839}, {727609, 853}, {734449, 857}, {737881, 859}, {744769, 863}, {769129, 877}, {776161, 881}, {779689, 883}, {786769, 887}, {822649, 907}, {829921, 911}, {844561, 919}, {863041, 929}, {877969, 937}, {885481, 941}, {896809, 947}, {908209, 953}, {935089, 967}, {942841, 971}, {954529, 977}, {966289, 983}, {982081, 991}, {994009, 997}};
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a%b);
}
ll T, MX;
ll a, b, c;
bool print_sub(pll x) {
if (x.first == 0 || x.second == 0) return 0;
if (x.first < 0 || x.second < 0) putchar('-');
if (x.first < 0) x.first = -x.first;
if (x.second < 0) x.second = -x.second;
if (x.second == 1) {
printf("%lld", x.first);
} else {
printf("%lld/%lld", x.first, x.second);
}
return 1;
}
bool print_sqrt(pll x, ll y, bool k) { // x/y*sqrt(z)
if (x.first == 0 || x.second == 0 || y == 0) return 0;
if (k) {
putchar('+');
}
if (x.first == 1 && x.second == 1) {
if (y == 1) printf("1");
else printf("sqrt(%lld)", y);
} else if (x.second == 1) {
if (y == 1) printf("%lld", x.first);
else printf("%lld*sqrt(%lld)", x.first, y);
} else if (x.first == 1) {
if (y == 1) printf("1/%lld", x.second);
else printf("sqrt(%lld)/%lld", y, x.second);
} else {
if (y == 1) printf("%lld/%lld", x.first, x.second);
else printf("%lld*sqrt(%lld)/%lld", x.first, y, x.second);
}
return 1;
}
pll simp_sqrt(ll delta) { // x*sqrt(y)
if (delta == 0) return {0, 0};
pll res = {1, 1};
for (int i = 0; i < 168; i++) {
while (!(delta%simpn2[i][0])) {
delta /= simpn2[i][0];
res.first *= simpn2[i][1];
}
}
res.second = delta;
return res;
}
pll simp_frac(pll x) { // x/y
if (x.first == 0 || x.second == 0) return x;
ll t = gcd(x.first, x.second);
x.first /= t, x.second /= t;
return x;
}
int main() {
T = read();
MX = read();
while (T--) {
a = read();
b = read();
c = read();
ll delta = b*b-4*a*c;
if (delta < 0) {
puts("NO");
continue;
}
// -3 -18 54
// delta: sqrt(972) = 18*sqrt(3)
pll sqrt_delta = simp_sqrt(delta);
// cout << sqrt_delta.first << " " << sqrt_delta.second << endl;
pll q1 = simp_frac({-b, 2*a});
pll q2 = simp_frac({sqrt_delta.first, 2*a});
if (q2.first < 0) q2.first = -q2.first;
if (q2.second < 0) q2.second = -q2.second;
ll r = sqrt_delta.second;
bool flg = 0;
if (r == 1) {
flg |= print_sub(simp_frac({q1.first*q2.second+q2.first*q1.second, q1.second*q2.second}));
} else {
if (q1.first != 0 && q1.second != 0) {
flg |= print_sub(q1);
}
flg |= print_sqrt(q2, r, flg);
}
if (!flg) printf("0");
puts("");
}
return 0;
}