CSP-J T3求hack悬关
  • 板块学术版
  • 楼主Ayano_
  • 当前回复6
  • 已保存回复7
  • 发布时间2023/10/25 18:30
  • 上次更新2023/11/2 11:26:47
查看原帖
CSP-J T3求hack悬关
536562
Ayano_楼主2023/10/25 18:30

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;
}
2023/10/25 18:30
加载中...