osa_k法 (Factorization Queries)
(Math/FactorizeQueries.hpp)

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "Math/FactorizeQueries.hpp"

概要

エラトステネスの篩の要領で前処理をしておくと素因数分解を高速にできる場合がある．

計算量

Mを素因数分解した最大の数とし，Nを素因数分解する時．

• 前処理 : O(M log(logM))
• クエリ : O(logN)

Code

// Precomputation : O(M log (log M)) (M : MAX)
// Factorize Query : O(log N) (N<=MAX)
template<int MAX>
struct FactorizeQueries{
    vector<int> min_factor;
    
    FactorizeQueries(){
        min_factor.resize(MAX+1);
        iota(begin(min_factor),end(min_factor),0);
        for(int i=2;i*i<=MAX;i++){
            if(min_factor[i]==i)
                for(int j=i+i;j<=MAX;j+=i) min_factor[j]=min(min_factor[j],i);
        }
    }
    
    vector<int> Factorize(int x){
        assert(x<=MAX);
        vector<int> ret;
        for(;x>1;x/=min_factor[x]) ret.push_back(min_factor[x]);
        return ret;
    }
};

#line 1 "Math/FactorizeQueries.hpp"
// Precomputation : O(M log (log M)) (M : MAX)
// Factorize Query : O(log N) (N<=MAX)
template<int MAX>
struct FactorizeQueries{
    vector<int> min_factor;
    
    FactorizeQueries(){
        min_factor.resize(MAX+1);
        iota(begin(min_factor),end(min_factor),0);
        for(int i=2;i*i<=MAX;i++){
            if(min_factor[i]==i)
                for(int j=i+i;j<=MAX;j+=i) min_factor[j]=min(min_factor[j],i);
        }
    }
    
    vector<int> Factorize(int x){
        assert(x<=MAX);
        vector<int> ret;
        for(;x>1;x/=min_factor[x]) ret.push_back(min_factor[x]);
        return ret;
    }
};

Back to top page