Sum of Rationals
(FPS/sumofRationals.hpp)

• View this file on GitHub
• Last update: 2023-01-16 20:41:46+09:00
• Include: #include "FPS/sumofRationals.hpp"

Required by

• $f(\exp(x))$ (FPS/compexp.hpp)

Code

#pragma once

template<typename T>pair<Poly<T>,Poly<T>> SumOfRationals(vector<pair<Poly<T>,Poly<T>>>& fs){
    using Ratio=pair<Poly<T>,Poly<T>>;
    if(fs.empty())return {Poly<T>({T(1)}),Poly<T>({T(1)})};
    sort(ALL(fs),[&](Ratio& a,Ratio& b){return a.first.size()+a.second.size()<b.first.size()+b.second.size();});
    deque<Ratio> deq;
    for(auto& f:fs)deq.push_back(f);
    while(deq.size()>1){
        auto [f,g]=deq[0];
        auto [p,q]=deq[1];
        deq.push_back({f*q+g*p,g*q});
        deq.pop_front();
        deq.pop_front();
    }
    return deq[0];
}

/**
 * @brief Sum of Rationals
*/

#line 2 "FPS/sumofRationals.hpp"

template<typename T>pair<Poly<T>,Poly<T>> SumOfRationals(vector<pair<Poly<T>,Poly<T>>>& fs){
    using Ratio=pair<Poly<T>,Poly<T>>;
    if(fs.empty())return {Poly<T>({T(1)}),Poly<T>({T(1)})};
    sort(ALL(fs),[&](Ratio& a,Ratio& b){return a.first.size()+a.second.size()<b.first.size()+b.second.size();});
    deque<Ratio> deq;
    for(auto& f:fs)deq.push_back(f);
    while(deq.size()>1){
        auto [f,g]=deq[0];
        auto [p,q]=deq[1];
        deq.push_back({f*q+g*p,g*q});
        deq.pop_front();
        deq.pop_front();
    }
    return deq[0];
}

/**
 * @brief Sum of Rationals
*/

Back to top page