1 条题解

  • 0
    @ 2025-5-4 19:23:55

    t 组输入，每组求一个大整数开立方根，输出一个小数，截断至小数点后 10 位（注意：是直接截断，不要四舍五入！），在结果前面输出一个校验和，该数字等于输出的数码之和对 10 取模。 和[HNOI2004]高精度开根 几乎一致，但是需要需要求小数点后 10 位并直接截断。实际上和这个模板题没有多少变化，只要在原始输入的数乘上一个 10的30次方，再做向下取整的牛顿迭代求高精度开根即可得到最终结果。

    typedef long long ll;
typedef unsigned long long ull;
const ull MODD = 998244353;
struct cd {
    double re, im;
 
    cd(double re = 0, double im = 0) : re(re), im(im) {}
 
    inline double real() const {
        return re;
    }
    inline double imag() const {
        return im;
    }
 
    inline void real(double re) {
        this->re = re;
    }
    inline void imag(double im) {
        this->im = im;
    }
 
    inline double norm() const {
        return re * re + im * im;
    }
 
    inline cd operator+(const cd& rhs) const {
        return cd(re + rhs.re, im + rhs.im);
    }
    inline cd operator-(const cd& rhs) const {
        return cd(re - rhs.re, im - rhs.im);
    }
    inline cd operator-() const {
        return cd(-re, -im);
    }
    inline cd operator*(const cd& rhs) const {
        return cd(re * rhs.re - im * rhs.im, re * rhs.im + im * rhs.re);
    }
    inline cd operator/(double x) const {
        return cd(re / x, im / x);
    }
 
    inline void operator+=(const cd& rhs) {
        re += rhs.re;
        im += rhs.im;
    }
    inline void operator/=(double x) {
        re /= x;
        im /= x;
    }
    inline void operator*=(const cd& rhs) {
        *this = *this * rhs;
    }
 
    inline friend cd conj(const cd& z) {
        return cd(z.re, -z.im);
    }
 
    inline cd operator/(const cd& rhs) const {
        return (*this * conj(rhs)) / rhs.norm();
    }
};
 
const int BASE = 4, MOD = 10000, LGM = 17;
const double PI = 3.1415926535897932384626;
 
class UnsignedDigit;
 
namespace DivHelper {
    UnsignedDigit quasiInv(const UnsignedDigit& v);
}
 
struct UnsignedDigit {
    vector<int> digits;
 
    UnsignedDigit() : digits(1) {}
 
    UnsignedDigit(const vector<int>& digits);
 
    UnsignedDigit(ll x);
 
    UnsignedDigit(char* str);
 
    void print() const;
 
    string print_format() const;
 
    ull trans_normal();
 
    bool operator<(const UnsignedDigit& rhs) const;
    bool operator<=(const UnsignedDigit& rhs) const;
    bool operator==(const UnsignedDigit& rhs) const;
 
    UnsignedDigit operator+(const UnsignedDigit& rhs) const;
    UnsignedDigit operator-(const UnsignedDigit& rhs) const;
    UnsignedDigit operator*(const UnsignedDigit& rhs) const;
    UnsignedDigit operator/(UnsignedDigit rhs) const;
 
    UnsignedDigit operator/(int v) const;
 
    UnsignedDigit move(int k) const;
 
    friend UnsignedDigit DivHelper::quasiInv(const UnsignedDigit& v);
 
    friend void swap(UnsignedDigit& lhs, UnsignedDigit& rhs) {
        swap(lhs.digits, rhs.digits);
    }
 
    void trim();
};
 
class UnsignedDecimal {};
 
class Int {};
 
class Decimal {};
 
namespace ConvHelper {
 
    struct FFT {
        int L;
        int brev[1 << 16];
        cd w[1 << 16];
 
        FFT() {}
 
        void init(int L) {
            this->L = L;
 
            for (int i = 0; i < (1 << L); ++i)
                brev[i] = (brev[i >> 1] >> 1) | ((i & 1) << (L - 1));
 
            for (int i = 0; i < 1 << L; ++i)
                w[i] = cd(cos(i * PI * 2 / (1 << L)), sin(i * PI * 2 / (1 << L)));
        }
 
        void dft(cd* a, int lgn, int d) {
            int n = 1 << lgn;
 
            for (int i = 0; i < n; ++i) {
                int rv = brev[i] >> (L - lgn);
 
                if (rv < i)
                    swap(a[rv], a[i]);
            }
 
            int fa = L;
 
            for (int t = 1; t < n; t <<= 1) {
                --fa;
 
                for (int i = 0; i < n; i += t << 1) {
                    cd* p = a + i;
 
                    for (int j = 0; j < t; ++j) {
                        cd x = p[j + t] * w[j << fa];
                        p[j + t] = p[j] - x;
                        p[j] += x;
                    }
                }
            }
 
            if (d == -1) {
                reverse(a + 1, a + n);
 
                for (int i = 0; i < n; ++i)
                    a[i] /= n;
            }
        }
 
        // realSeq FFT
        void dft(cd* a, cd* b, int lgn, int d) {
            int n = 1 << lgn;
 
            for (int i = 0; i < n; ++i)
                a[i].imag(b[i].real());
 
            dft(a, lgn, d);
            b[0] = conj(a[0]);
 
            for (int i = 1; i < n; ++i)
                b[i] = conj(a[n - i]);
 
            for (int i = 0; i < n; ++i) {
                cd x = a[i], y = b[i];
                a[i] = (x + y) / 2.;
                b[i] = (x - y) / cd(0, 2);
            }
        }
 
    } fft;
 
    vector<ll> conv(const vector<int>& a, const vector<int>& b) {
        int n = a.size() - 1, m = b.size() - 1;
 
        if (n < 100 / (m + 1) || n < 3 || m < 3) {
            vector<ll> ret(n + m + 1);
 
            for (int i = 0; i <= n; ++i)
                for (int j = 0; j <= m; ++j)
                    ret[i + j] += a[i] * (ll)b[j];
 
            return ret;
        }
 
        int lgn = 0;
 
        while ((1 << lgn) <= n + m)
            ++lgn;
 
        vector<cd> ta(a.begin(), a.end()), tb(b.begin(), b.end());
        ta.resize(1 << lgn);
        tb.resize(1 << lgn);
 
        if (a == b) {
            fft.dft(ta.begin().base(), lgn, 1);
            tb = ta;
        }
        else
            fft.dft(ta.begin().base(), tb.begin().base(), lgn, 1);
 
        for (int i = 0; i < (1 << lgn); ++i)
            ta[i] *= tb[i];
 
        fft.dft(ta.begin().base(), lgn, -1);
        vector<ll> ret(n + m + 1);
 
        for (int i = 0; i <= n + m; ++i)
            ret[i] = ta[i].real() + 0.5;
 
        return ret;
    }
 
}
 
namespace DivHelper {
 
    UnsignedDigit quasiInv(const UnsignedDigit& v) {
        if (v.digits.size() == 1) {
            UnsignedDigit tmp;
            tmp.digits.resize(3);
            tmp.digits[2] = 1;
            return tmp / v.digits[0];
        }
 
        if (v.digits.size() == 2) {
            UnsignedDigit sum = 0LL, go = 1;
            vector<int> tmp(4);
            go = go.move(4);
            vector<UnsignedDigit> db(LGM);
            db[0] = v;
 
            for (int i = 1; i < LGM; ++i)
                db[i] = db[i - 1] + db[i - 1];
 
            for (int i = 3; i >= 0; --i) {
                for (int k = LGM - 1; k >= 0; --k)
                    if (sum + db[k].move(i) <= go) {
                        sum = sum + db[k].move(i);
                        tmp[i] |= 1 << k;
                    }
            }
 
            return tmp;
        }
 
        int n = v.digits.size(), k = (n + 2) / 2;
        UnsignedDigit tmp = quasiInv(vector<int>(v.digits.end().base() - k, v.digits.end().base()));
        return (UnsignedDigit(2) * tmp).move(n - k) - (v * (tmp * tmp)).move(-2 * k);
    }
 
}
 
UnsignedDigit::UnsignedDigit(ll x) {
    while (x) {
        digits.push_back(x % MOD);
        x /= MOD;
    }
 
    if (digits.empty())
        digits.push_back(0);
}
 
UnsignedDigit UnsignedDigit::move(int k) const {
    if (k == 0)
        return *this;
 
    if (k < 0) {
        if (-k >= digits.size())
            return UnsignedDigit();
 
        return vector<int>(digits.begin().base() + (-k), digits.end().base());
    }
 
    if (digits.size() == 1 && digits[0] == 0)
        return UnsignedDigit();
 
    UnsignedDigit ret;
    ret.digits.resize(k, 0);
    ret.digits.insert(ret.digits.end(), digits.begin(), digits.end());
    return ret;
}
 
bool UnsignedDigit::operator<(const UnsignedDigit& rhs) const {
    int n = digits.size(), m = rhs.digits.size();
 
    if (n != m)
        return n < m;
 
    for (int i = n - 1; i >= 0; --i)
        if (digits[i] != rhs.digits[i])
            return digits[i] < rhs.digits[i];
 
    return false;
}
 
bool UnsignedDigit::operator<=(const UnsignedDigit& rhs) const {
    int n = digits.size(), m = rhs.digits.size();
 
    if (n != m)
        return n < m;
 
    for (int i = n - 1; i >= 0; --i)
        if (digits[i] != rhs.digits[i])
            return digits[i] < rhs.digits[i];
 
    return true;
}
 
bool UnsignedDigit::operator==(const UnsignedDigit& rhs) const {
    int n = digits.size(), m = rhs.digits.size();
 
    if (n != m)
        return false;
 
    return memcmp(digits.begin().base(), rhs.digits.begin().base(), n) == 0;
}
 
UnsignedDigit UnsignedDigit::operator+(const UnsignedDigit& rhs) const {
    int n = digits.size(), m = rhs.digits.size();
    vector<int> tmp = digits;
 
    if (m > n) {
        tmp.resize(m + 1);
 
        for (int i = 0; i < m; ++i)
            if ((tmp[i] += rhs.digits[i]) >= MOD) {
                tmp[i] -= MOD;
                ++tmp[i + 1];
            }
    }
    else {
        tmp.resize(n + 1);
 
        for (int i = 0; i < m; ++i)
            if ((tmp[i] += rhs.digits[i]) >= MOD) {
                tmp[i] -= MOD;
                ++tmp[i + 1];
            }
 
        for (int i = m; i < n; ++i)
            if (tmp[i] == MOD) {
                tmp[i] = 0;
                ++tmp[i + 1];
            }
    }
 
    return tmp;
}
 
UnsignedDigit UnsignedDigit::operator*(const UnsignedDigit& rhs) const {
    vector<ll> tmp = ConvHelper::conv(digits, rhs.digits);
 
    for (int i = 0; i + 1 < tmp.size(); ++i) {
        tmp[i + 1] += tmp[i] / MOD;
        tmp[i] %= MOD;
    }
 
    while (tmp.back() >= MOD) {
        ll remain = tmp.back() / MOD;
        tmp.back() %= MOD;
        tmp.push_back(remain);
    }
 
    return vector<int>(tmp.begin(), tmp.end());
}
 
UnsignedDigit UnsignedDigit::operator/(UnsignedDigit rhs) const {
    int m = digits.size(), n = rhs.digits.size(), t = 0;
 
    if (m < n)
        return 0LL;
 
    if (m > n * 2)
        t = m - 2 * n;
 
    rhs = DivHelper::quasiInv(rhs.move(t));
    UnsignedDigit ret = move(t) * rhs;
    return ret.move(-2 * (n + t));
}
 
UnsignedDigit UnsignedDigit::operator/(int k) const {
    UnsignedDigit ret;
    int n = digits.size();
    ret.digits.resize(n);
    ll r = 0;
 
    for (int i = n - 1; i >= 0; --i) {
        r = r * MOD + digits[i];
        ret.digits[i] = r / k;
        r %= k;
    }
 
    ret.trim();
    return ret;
}
 
UnsignedDigit UnsignedDigit::operator-(const UnsignedDigit& rhs) const {
    UnsignedDigit ret(*this);
    int n = rhs.digits.size();
 
    for (int i = 0; i < n; ++i)
        if ((ret.digits[i] -= rhs.digits[i]) < 0) {
            ret.digits[i] += MOD;
            --ret.digits[i + 1];
        }
 
    ret.trim();
    return ret;
}
 
UnsignedDigit::UnsignedDigit(const vector<int>& digits) : digits(digits) {
    if (this->digits.empty())
        this->digits.resize(1);
 
    trim();
}
 
void UnsignedDigit::trim() {
    while (digits.size() > 1 && digits.back() == 0)
        digits.pop_back();
}
 
 
 
void UnsignedDigit::print() const {
    printf("%d", digits.back());
    int j = 0;
 
    for (int i = (int)digits.size() - 2; i >= 0; --i) {
        printf("%04d", digits[i]);
        ++j;
    }
 
    //putchar('\n');
}
 
string UnsignedDigit::print_format() const {
    static char s[20];
    memset(s, 0, sizeof(s));
    string ret = "";
    sprintf(s, "%d", digits.back());
    ret += string(s);
    int j = 0;
 
    for (int i = (int)digits.size() - 2; i >= 0; --i) {
        sprintf(s, "%04d", digits[i]);
        ret += string(s);
        ++j;
    }
    return ret;
    //putchar('\n');
}
 
 
ull UnsignedDigit::trans_normal() {
    ull ret = 0;
    ull wid = 1;
 
    for (int i = 0; i < (int)digits.size(); ++i) {
        ret += digits[i] * wid;
        wid *= 10000;
    }
 
    return ret;
}
 
UnsignedDigit::UnsignedDigit(char* str) {
    int n = strlen(str);
    reverse(str, str + n);
    digits.resize((n + BASE - 1) / BASE);
    int cur = 1;
 
    for (int i = 0; i < n; ++i) {
        if (i % BASE == 0)
            cur = 1;
 
        digits[i / BASE] += cur * (str[i] - '0');
        cur *= 10;
    }
 
    trim();
}
 
char s[1000010];
 
void div(UnsignedDigit& a, UnsignedDigit& b, UnsignedDigit& res) {
    res = a / b;
 
    while ((res + 1) * b <= a)
        res = res + 1;
 
    while (a < res * b)
        res = res - 1;
 
}
UnsignedDigit pow(const UnsignedDigit& a, int b) {
    UnsignedDigit tmp = a, ans = 1;
    while (b) {
        if (b & 1) ans = ans * tmp;
        b >>= 1;
        tmp = tmp * tmp;
    }
    return ans;
}
int t;
UnsignedDigit ans, tmp_ans, tmp_div, tmp_pow;
int len_n, len_ans;
int m;
int main() {
    int l = ceil(log2(10086));
    ConvHelper::fft.init(l + 2);
    scanf("%d", &t);
    while (t--) {
 
        m = 3;
        scanf("%s", s);
        len_n = strlen(s);
        //for(int i = len_n; i < len_n + 30; ++i) s[i] = '0'; s[len_n + 30] = '\0';
        strcat(s, "000000000000000000000000000000");
        //if (!strcmp(s, "0")) { puts("0 0.0000000000"); continue; }
        UnsignedDigit a(s);
        len_n = strlen(s);
        //int l = ceil(log2(len_n));
        //ConvHelper::fft.init(l + 2);
 
        len_ans = (len_n + m - 1) / m;
 
        ans = 9999;
        ans = ans.move((len_ans) / 4);
 
        int lo = 0, hi = 9999, mi = 0;
        while (lo < hi) {
            mi = (lo + hi) >> 1;
            ans.digits.back() = mi;
            if (pow(ans, m) <= a) lo = mi + 1;
            else hi = mi;
        }
 
        ans.digits.back() = lo;
        ans.trim();
 
        tmp_pow = pow(ans, m - 1);
        div(a, tmp_pow, tmp_div);
        tmp_ans = (ans * (m - 1) + tmp_div) / m;
        while (tmp_ans < ans) {
            ans = tmp_ans;
            tmp_pow = pow(ans, m - 1);
            div(a, tmp_pow, tmp_div);
            tmp_ans = (ans * (m - 1) + tmp_div) / m;
        }
        string output = ans.print_format();
        int test_sum = 0;
        for (int i = 0; i < output.length(); ++i) test_sum += output[i] - 48, test_sum = test_sum >= 10 ? test_sum - 10 : test_sum;
        printf("%d ", test_sum);
        for (int i = 0; i < output.length() - 10; ++i) putchar(output[i]);
        putchar('.');
        for (int i = output.length() - 10; i < output.length(); ++i) putchar(output[i]);
        putchar('\n');
    }
    return 0;
}
    • 1

    Cube Root

    信息

    ID
    966
    时间
    1000ms
    内存
    256MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 评测队列
    2. 服务状态
    3. 兼容模式
    4. 主题
    2. 黔ICP备2023002402号-2
    3. Worker 0, 34ms
    4. Powered by Hydro v4.19.1 Community, Modified by 33DAI