template/utils.hpp

• View this file on GitHub
• Last update: 2024-07-01 23:39:10+09:00
• Include: #include "template/utils.hpp"

Required by

• data_structure/binary_indexed_tree.hpp
• data_structure/binary_trie.hpp
• data_structure/dynamic_segment_tree.hpp
• data_structure/fenwick_tree.hpp
• data_structure/lazy_segment_tree.hpp
• data_structure/li_chao_tree.hpp
• data_structure/offline_rectangle_sum.hpp
• data_structure/range_tree.hpp
• fps/formal_power_series.hpp
• fps/fps_arbitrary.hpp
• fps/fps_atcoder.hpp
• fps/fps_modint.hpp
• fps/fps_ntt.hpp
• fps/multipoint_evaluation.hpp
• fps/ntt.hpp
• fps/relaxed_convolution.hpp
• fps/sample_point_shift.hpp
• geometry/base_ld.hpp
• geometry/partition_by_circle.hpp
• graph/graph_query.hpp
• math/gcd_convolution.hpp
• math/lcm_convolution.hpp
• math/sieve.hpp
• misc/QMC.hpp
• misc/inversion.hpp
• misc/local_minimum.hpp
• misc/mex.hpp
• misc/mo_algorithm.hpp
• misc/random_tree.hpp
• misc/rng.hpp
• string/rolling_hash.hpp
• template/template.hpp
• Mo on Tree (tree/Mo_on_Tree.hpp)
• tree/tree_query_weighted.hpp

Verified with

• test/data_structure/Cycle_Detection_Undirected_vector2d.test.cpp
• test/data_structure/Line_Add_Get_Min.test.cpp
• test/data_structure/PointAddRangeSum.test.cpp
• test/data_structure/Point_Add_Rectangle_Sum.test.cpp
• test/data_structure/Point_Set_Range_Composite.test.cpp
• test/data_structure/Point_Set_Range_Composite_dynamic_segment_tree.test.cpp
• test/data_structure/RangeParallelUnionfind.test.cpp
• test/data_structure/Range_Affine_Range_Sum.test.cpp
• test/data_structure/Rectangle_Sum.test.cpp
• test/data_structure/Segment_Add_Get_Min.test.cpp
• test/data_structure/SetXorMin.test.cpp
• test/data_structure/Static_RMQ.test.cpp
• test/data_structure/Static_Range_Inversions_Query.test.cpp
• test/data_structure/Unionfind.test.cpp
• test/data_structure/Unionfind_with_Potential_NonCommutative_Group.test.cpp
• test/data_structure/aoj1068_segtree2d.test.cpp
• test/data_structure/aoj_2235.test.cpp
• test/data_structure/aoj_dsl_1_b.test.cpp
• test/data_structure/yuki_1077.test.cpp
• test/fps/Convolution1000000007.test.cpp
• test/fps/Inv_of_Formal_Power_Series.test.cpp
• test/fps/Multipoint_Evaluation_Geometric_Sequence.test.cpp
• test/fps/Shift_of_Sampling_Points_of_Polynomial.test.cpp
• test/fps/convolution.test.cpp
• test/fps/convolution_relaxed_convolution.test.cpp
• test/fps998244353/Division_of_Polynomials_998244353.test.cpp
• test/fps998244353/Kth_term_of_Linearly_Recurrent_Sequence.test.cpp
• test/fps998244353/convolution_998244353.test.cpp
• test/fps998244353/multipoint_evaluation_998244353.test.cpp
• test/fps998244353/multipoint_evaluation_geo_998244353.test.cpp
• test/fps998244353/polynomial_taylor_shift_998244353.test.cpp
• test/fps998244353/shift_of_sampling_points_of_polynomial_998244353.test.cpp
• test/geometry/aoj1198.test.cpp
• test/graph/CycleDetectionDirected.test.cpp
• test/graph/Shortest_Path.test.cpp
• test/graph/Shortest_Path2.test.cpp
• test/graph/Strongly_Connected_Components.test.cpp
• test/math/Binomial_Coefficient_Prime_Mod.test.cpp
• test/math/Binomial_Coefficient_Prime_Mod_modintnew.test.cpp
• test/math/CountingEulerianCircuits.test.cpp
• test/math/CountingPrimes.test.cpp
• test/math/Determinant_of_Matrix.test.cpp
• test/math/Gcd_Convolution.test.cpp
• test/math/Lcm_Convolution.test.cpp
• test/math/PrimitiveRoot.test.cpp
• test/math/Sum_of_Floor_of_Linear.test.cpp
• test/math/SumofMultiplicativeFunction.test.cpp
• test/misc/LongestIncreasingSubsequence.test.cpp
• test/misc/StaticRangeModeQuery.test.cpp
• test/string/Eertree.test.cpp
• test/string/RunEnumerate.test.cpp
• test/string/SuffixArray.test.cpp
• test/string/Z_Algorithm.test.cpp
• test/tree/FrequencyTableofTreeDistance.test.cpp
• test/tree/Jump_on_Tree.test.cpp
• test/tree/Jump_on_Tree_hld.test.cpp
• test/tree/Lowest_Common_Ancestor.test.cpp
• test/tree/Rerooting_DP.test.cpp
• test/tree/Tree_Diameter_hld.test.cpp
• test/tree/VertexSetPathComposite.test.cpp
• test/tree/Vertex_Add_Path_Sum.test.cpp
• test/tree/aoj_0489.test.cpp

Code

#pragma once

#include <cmath>
#include <vector>
#include <algorithm>

namespace noya2{

unsigned long long inner_binary_gcd(unsigned long long a, unsigned long long b){
    if (a == 0 || b == 0) return a + b;
    int n = __builtin_ctzll(a); a >>= n;
    int m = __builtin_ctzll(b); b >>= m;
    while (a != b) {
        int mm = __builtin_ctzll(a - b);
        bool f = a > b;
        unsigned long long c = f ? a : b;
        b = f ? b : a;
        a = (c - b) >> mm;
    }
    return a << std::min(n, m);
}

template<typename T> T gcd_fast(T a, T b){ return static_cast<T>(inner_binary_gcd(std::abs(a),std::abs(b))); }

long long sqrt_fast(long long n) {
    if (n <= 0) return 0;
    long long x = sqrt(n);
    while ((x + 1) * (x + 1) <= n) x++;
    while (x * x > n) x--;
    return x;
}

template<typename T> T floor_div(const T n, const T d) {
    assert(d != 0);
    return n / d - static_cast<T>((n ^ d) < 0 && n % d != 0);
}

template<typename T> T ceil_div(const T n, const T d) {
    assert(d != 0);
    return n / d + static_cast<T>((n ^ d) >= 0 && n % d != 0);
}

template<typename T> void uniq(std::vector<T> &v){
    std::sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}

template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }

template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }

template<typename T> inline bool range(T l, T x, T r){ return l <= x && x < r; }

} // namespace noya2

#line 2 "template/utils.hpp"

#include <cmath>
#include <vector>
#include <algorithm>

namespace noya2{

unsigned long long inner_binary_gcd(unsigned long long a, unsigned long long b){
    if (a == 0 || b == 0) return a + b;
    int n = __builtin_ctzll(a); a >>= n;
    int m = __builtin_ctzll(b); b >>= m;
    while (a != b) {
        int mm = __builtin_ctzll(a - b);
        bool f = a > b;
        unsigned long long c = f ? a : b;
        b = f ? b : a;
        a = (c - b) >> mm;
    }
    return a << std::min(n, m);
}

template<typename T> T gcd_fast(T a, T b){ return static_cast<T>(inner_binary_gcd(std::abs(a),std::abs(b))); }

long long sqrt_fast(long long n) {
    if (n <= 0) return 0;
    long long x = sqrt(n);
    while ((x + 1) * (x + 1) <= n) x++;
    while (x * x > n) x--;
    return x;
}

template<typename T> T floor_div(const T n, const T d) {
    assert(d != 0);
    return n / d - static_cast<T>((n ^ d) < 0 && n % d != 0);
}

template<typename T> T ceil_div(const T n, const T d) {
    assert(d != 0);
    return n / d + static_cast<T>((n ^ d) >= 0 && n % d != 0);
}

template<typename T> void uniq(std::vector<T> &v){
    std::sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}

template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }

template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }

template<typename T> inline bool range(T l, T x, T r){ return l <= x && x < r; }

} // namespace noya2

Back to top page