library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Resultant
(FPS/resultant.hpp)

• View this file on GitHub
• Last update: 2025-05-11 13:37:16+09:00
• Include: #include "FPS/resultant.hpp"

Code

#pragma once

template <typename T> T Resultant(Poly<T> f, Poly<T> g) {
    if (g.empty()) {
        if (SZ(f) == 1)
            return 1;
        else
            return 0;
    }
    bool sign = 0;
    T ret = 1;
    for (;;) {
        auto [q, r] = f.divmod(g);
        if (r.empty()) {
            if (SZ(g) == 1)
                ret *= g[0].pow(f.deg());
            else
                ret = 0;
            break;
        } else {
            if (f.deg() & 1 and g.deg() & 1)
                sign ^= 1;
            ret *= g.back().pow(f.deg() - r.deg());
            swap(f, g);
            g = r;
        }
    }
    if (sign)
        ret = -ret;
    return ret;
}

/**
 * @brief Resultant
 */

#line 2 "FPS/resultant.hpp"

template <typename T> T Resultant(Poly<T> f, Poly<T> g) {
    if (g.empty()) {
        if (SZ(f) == 1)
            return 1;
        else
            return 0;
    }
    bool sign = 0;
    T ret = 1;
    for (;;) {
        auto [q, r] = f.divmod(g);
        if (r.empty()) {
            if (SZ(g) == 1)
                ret *= g[0].pow(f.deg());
            else
                ret = 0;
            break;
        } else {
            if (f.deg() & 1 and g.deg() & 1)
                sign ^= 1;
            ret *= g.back().pow(f.deg() - r.deg());
            swap(f, g);
            g = r;
        }
    }
    if (sign)
        ret = -ret;
    return ret;
}

/**
 * @brief Resultant
 */

Back to top page