mod/crt3.hpp

• View this file on GitHub
• Last update: 2024-06-11 19:14:48+09:00
• Include: #include "mod/crt3.hpp"

Required by

• bigint/base.hpp
• bigint/binary.hpp
• graph/characteristic_polynomial_of_tree_adjacency_matrix.hpp
• graph/chromatic.hpp
• graph/count/count_clique.hpp
• graph/count/count_independent_set.hpp
• graph/count/count_labeled_biconnected.hpp
• graph/count/count_labeled_bipartite.hpp
• graph/count/count_labeled_bridgeless.hpp
• graph/count/count_labeled_connected.hpp
• graph/count/count_labeled_dag.hpp
• graph/count/count_labeled_eulerian.hpp
• graph/count/count_labeled_forest.hpp
• graph/count/count_labeled_strong_digraph.hpp
• graph/count/count_labeled_strong_tournament.hpp
• graph/count/count_labeled_unicyclic.hpp
• graph/count/count_unlabeled_tree.hpp
• graph/count_matching_on_tree.hpp
• graph/tree_all_distances.hpp
• graph/tree_walk_generating_function.hpp
• linalg/blackbox/pascal.hpp
• linalg/blackbox/vandermonde.hpp
• linalg/det_A_plus_xB.hpp
• mod/multiplicative_convolution_mod_2n.hpp
• mod/multiplicative_convolution_mod_p.hpp
• new_poly/base.hpp
• poly/coef_of_rational_fps.hpp
• poly/coef_of_rational_fps_2d.hpp
• poly/composed_product.hpp
• poly/composed_sum.hpp
• poly/composition.hpp
• poly/composition_f_1_minus_ex.hpp
• poly/composition_f_a_plus_bx.hpp
• poly/composition_f_a_plus_bx_div_c_plus_dx.hpp
• poly/composition_f_ex.hpp
• poly/composition_f_ex_minus_1.hpp
• poly/composition_f_log_1_minus_x.hpp
• poly/composition_f_x_plus_1x.hpp
• poly/compositional_inverse.hpp
• poly/convolution.hpp
• poly/convolution2d.hpp
• poly/convolution_all.hpp
• poly/convolution_huge.hpp
• poly/convolution_leq.hpp
• poly/convolution_u64.hpp
• poly/finding_root_of_polynomial.hpp
• poly/fps_div.hpp
• poly/fps_exp.hpp
• poly/fps_inv.hpp
• poly/fps_inv_2d.hpp
• poly/fps_log.hpp
• poly/fps_pow.hpp
• poly/fps_sqrt.hpp
• poly/from_log_differentiation.hpp
• poly/lagrange_interpolate_iota.hpp
• poly/middle_product.hpp
• poly/multipoint.hpp
• poly/multivar_convolution.hpp
• poly/multivar_convolution_cyclic.hpp
• poly/online/online_convolution_garner.hpp
• poly/online/online_exp_garner.hpp
• poly/partial_frac_decomposition_1.hpp
• poly/poly_divmod.hpp
• poly/poly_gcd.hpp
• poly/poly_mod_pow.hpp
• poly/poly_taylor_shift.hpp
• poly/power_projection.hpp
• poly/prefix_product_of_poly.hpp
• poly/prefix_sum_of_polynomial.hpp
• poly/product_of_f_rk_x.hpp
• poly/product_of_one_minus_xn.hpp
• poly/product_of_one_plus_xn.hpp
• poly/product_of_pow_of_linear.hpp
• poly/slice_rational_fps.hpp
• poly/sparse_exp_of_div.hpp
• poly/sum_of_exp_bx.hpp
• poly/sum_of_power_of_roots.hpp
• poly/sum_of_prefix_suffix_products.hpp
• poly/sum_of_rationals.hpp
• poly/typical_divide_conquer.hpp
• seq/count_grid_path.hpp
• seq/famous/bell_number.hpp
• seq/famous/bell_number_large.hpp
• seq/famous/bernoulli.hpp
• seq/famous/eulerian_number.hpp
• seq/famous/indecomposable_permutations.hpp
• seq/famous/partition_number.hpp
• seq/famous/riemann_zeta_even.hpp
• seq/famous/stirling_number_1.hpp
• seq/famous/stirling_number_2.hpp
• seq/famous/surjection.hpp
• seq/interpolate_linear_rec.hpp
• seq/interpolate_poly_exp_sum.hpp
• seq/kth_term_of_p_recursive.hpp
• seq/sum_of_powers.hpp
• setfunc/power_projection_of_sps.hpp
• string/wildcard_pattern_matching.hpp
• test/library_checker/graph/count_spanning_tree_directed_sparse_test.cpp

Verified with

• graph/chromatic_polynomial.test.cpp
• test/aoj/NTL_2_A.test.cpp
• test/aoj/NTL_2_B.test.cpp
• test/aoj/NTL_2_C.test.cpp
• test/library_checker/bigint/addition_of_bigintegers.test.cpp
• test/library_checker/bigint/multiplication_of_bigintegers.test.cpp
• test/library_checker/convolution/convolution_huge.test.cpp
• test/library_checker/convolution/convolution_mod.test.cpp
• test/library_checker/convolution/convolution_mod_107.test.cpp
• test/library_checker/convolution/convolution_mod_107_dmint.test.cpp
• test/library_checker/convolution/convolution_mod_2_64.test.cpp
• test/library_checker/convolution/convolution_mod_dmint.test.cpp
• test/library_checker/convolution/convolution_mod_setntt.test.cpp
• test/library_checker/convolution/mul_mod2n_convolution.test.cpp
• test/library_checker/convolution/mul_modp_conv.test.cpp
• test/library_checker/convolution/multivariate_convolution.test.cpp
• test/library_checker/convolution/subset_convolution_multivar.test.cpp
• test/library_checker/graph/chromatic_number.test.cpp
• test/library_checker/math/bernoulli.test.cpp
• test/library_checker/math/factorial.test.cpp
• test/library_checker/math/kth_term_of_linearly_recurrent_sequence.test.cpp
• test/library_checker/math/multivariate_convolution_cyclic.test.cpp
• test/library_checker/math/partition.test.cpp
• test/library_checker/math/power_projection_of_sps.test.cpp
• test/library_checker/math/powproj_sps.test.cpp
• test/library_checker/math/sharp_p_subset_sum.test.cpp
• test/library_checker/math/stirling_number_of_the_first_kind.test.cpp
• test/library_checker/math/stirling_number_of_the_first_kind_fixed_k.test.cpp
• test/library_checker/math/stirling_number_of_the_second_kind.test.cpp
• test/library_checker/math/sum_of_exp_times_poly.test.cpp
• test/library_checker/polynomial/composition_dmint.test.cpp
• test/library_checker/polynomial/composition_of_fps.test.cpp
• test/library_checker/polynomial/compositional_inverse.test.cpp
• test/library_checker/polynomial/compositional_inverse_dmint.test.cpp
• test/library_checker/polynomial/exp_of_fps.test.cpp
• test/library_checker/polynomial/exp_of_fps_dmint.test.cpp
• test/library_checker/polynomial/exp_of_fps_sparse.test.cpp
• test/library_checker/polynomial/exp_of_fps_sparse_dmint.test.cpp
• test/library_checker/polynomial/inv_of_fps.test.cpp
• test/library_checker/polynomial/inv_of_fps_dmint.test.cpp
• test/library_checker/polynomial/inv_of_fps_sparse.test.cpp
• test/library_checker/polynomial/inv_of_fps_sparse_dmint.test.cpp
• test/library_checker/polynomial/inv_of_polynomials.test.cpp
• test/library_checker/polynomial/log_of_fps.test.cpp
• test/library_checker/polynomial/log_of_fps_dmint.test.cpp
• test/library_checker/polynomial/log_of_fps_sparse.test.cpp
• test/library_checker/polynomial/log_of_fps_sparse_dmint.test.cpp
• test/library_checker/polynomial/multipoint_evaluation.test.cpp
• test/library_checker/polynomial/multipoint_evaluation_on_geom.test.cpp
• test/library_checker/polynomial/multipoint_evaluation_on_geom_2.test.cpp
• test/library_checker/polynomial/polynomial_division.test.cpp
• test/library_checker/polynomial/polynomial_interpolation.test.cpp
• test/library_checker/polynomial/polynomial_interpolation_on_geom.test.cpp
• test/library_checker/polynomial/polynomial_taylor_shift.test.cpp
• test/library_checker/polynomial/pow_of_fps.test.cpp
• test/library_checker/polynomial/pow_of_fps_dmint.test.cpp
• test/library_checker/polynomial/pow_of_fps_sparse.test.cpp
• test/library_checker/polynomial/pow_of_fps_sparse_dmint.test.cpp
• test/library_checker/polynomial/product_of_polynomial_sequence.test.cpp
• test/library_checker/polynomial/shift_of_sampling_points_of_polynomial.test.cpp
• test/library_checker/polynomial/slice_rational.test.cpp
• test/library_checker/polynomial/sqrt_of_fps.test.cpp
• test/library_checker/polynomial/sqrt_of_fps_sparse.test.cpp
• test/library_checker/sample/aplusb128.test.cpp
• test/library_checker/tree/frequency_table_of_tree_distance.test.cpp
• test/library_checker/tree/frequency_table_of_tree_distance_0.test.cpp
• test/library_checker/tree/frequency_table_of_tree_distance_2.test.cpp
• test/mytest/bell.test.cpp
• test/mytest/bell_number.test.cpp
• test/mytest/bigint.test.cpp
• test/mytest/catalan_convolution.test.cpp
• test/mytest/chirp_z.test.cpp
• test/mytest/coef_of_rational.test.cpp
• test/mytest/composition_1_minus_ex.test.cpp
• test/mytest/composition_ex_minus_1.test.cpp
• test/mytest/composition_f_x_plus_1x.test.cpp
• test/mytest/composition_log_1_minus_x.test.cpp
• test/mytest/compositional_inverset.test.cpp
• test/mytest/conv2d.test.cpp
• test/mytest/conv_leq.test.cpp
• test/mytest/convolution_all_1.test.cpp
• test/mytest/count_bipartite.test.cpp
• test/mytest/count_clique.test.cpp
• test/mytest/count_indep_set.test.cpp
• test/mytest/count_labeled_biconnected.test.cpp
• test/mytest/count_labeled_bridgeless.test.cpp
• test/mytest/count_labeled_connected.test.cpp
• test/mytest/count_labeled_dag.test.cpp
• test/mytest/count_labeled_eulerian.test.cpp
• test/mytest/count_labeled_forest.test.cpp
• test/mytest/count_labeled_strong.test.cpp
• test/mytest/count_labeled_tournament.test.cpp
• test/mytest/count_unlabeled_tree.test.cpp
• test/mytest/enum_partitions.test.cpp
• test/mytest/eulerian_number.test.cpp
• test/mytest/factorial_998.test.cpp
• test/mytest/graph_count.test.cpp
• test/mytest/online_division.test.cpp
• test/mytest/online_exp.test.cpp
• test/mytest/online_inv.test.cpp
• test/mytest/online_log.test.cpp
• test/mytest/online_pow.test.cpp
• test/mytest/online_square.test.cpp
• test/mytest/partial_frac.test.cpp
• test/mytest/pascal.test.cpp
• test/mytest/poly_root_finding.test.cpp
• test/mytest/power_projection.test.cpp
• test/mytest/product_of_one_pm_xn.test.cpp
• test/mytest/simple_perm.test.cpp
• test/mytest/sparse_pow_2d.test.cpp
• test/mytest/tree_walk_gf.test.cpp
• test/mytest/typical_dc.test.cpp
• test/mytest/vandermonde.test.cpp
• test/yukicoder/1080.test.cpp
• test/yukicoder/1080_2.test.cpp
• test/yukicoder/1145.test.cpp
• test/yukicoder/1303.test.cpp
• test/yukicoder/1321.test.cpp
• test/yukicoder/1357.test.cpp
• test/yukicoder/1392.test.cpp
• test/yukicoder/1500.test.cpp
• test/yukicoder/1516.test.cpp
• test/yukicoder/1533.test.cpp
• test/yukicoder/1547.test.cpp
• test/yukicoder/1549.test.cpp
• test/yukicoder/1561.test.cpp
• test/yukicoder/1575.test.cpp
• test/yukicoder/1618.test.cpp
• test/yukicoder/1685.test.cpp
• test/yukicoder/1720.test.cpp
• test/yukicoder/1755.test.cpp
• test/yukicoder/1783.test.cpp
• test/yukicoder/1796.test.cpp
• test/yukicoder/1796_1.test.cpp
• test/yukicoder/1821.test.cpp
• test/yukicoder/1844.test.cpp
• test/yukicoder/1857.test.cpp
• test/yukicoder/1875.test.cpp
• test/yukicoder/1907.test.cpp
• test/yukicoder/1939.test.cpp
• test/yukicoder/1962.test.cpp
• test/yukicoder/2005.test.cpp
• test/yukicoder/2062.test.cpp
• test/yukicoder/2097.test.cpp
• test/yukicoder/2108.test.cpp
• test/yukicoder/2122.test.cpp
• test/yukicoder/2166.test.cpp
• test/yukicoder/2231.test.cpp
• test/yukicoder/2243.test.cpp
• test/yukicoder/2305.test.cpp
• test/yukicoder/2440.test.cpp
• test/yukicoder/2459.test.cpp
• test/yukicoder/2508.test.cpp
• test/yukicoder/2525.test.cpp
• test/yukicoder/2580.test.cpp
• test/yukicoder/2583.test.cpp
• test/yukicoder/2587.test.cpp
• test/yukicoder/2587_2.test.cpp
• test/yukicoder/2613.test.cpp
• test/yukicoder/2626.test.cpp
• test/yukicoder/2649.test.cpp
• test/yukicoder/2801.test.cpp
• test/yukicoder/303.test.cpp
• test/yukicoder/502_2.test.cpp
• test/yukicoder/541.test.cpp
• test/yukicoder/578.test.cpp
• test/yukicoder/579.test.cpp
• test_atcoder/abc222h.test.cpp
• test_atcoder/abc222h_2.test.cpp
• test_atcoder/abc241h.test.cpp
• test_atcoder/abc253h.test.cpp
• test_atcoder/abc260h.test.cpp
• test_atcoder/abc267g.test.cpp
• test_atcoder/abc267h.test.cpp
• test_atcoder/abc269ex.test.cpp
• test_atcoder/abc269ex2.test.cpp
• test_atcoder/abc272_h.test.cpp
• test_atcoder/abc276_g.test.cpp
• test_atcoder/abc276_g_2.test.cpp
• test_atcoder/abc281g.test.cpp
• test_atcoder/abc285h.test.cpp
• test_atcoder/abc288ex.test.cpp
• test_atcoder/abc318h.test.cpp
• test_atcoder/abc331g.test.cpp
• test_atcoder/abc333f.test.cpp
• test_atcoder/abc339f.test.cpp
• test_atcoder/abc345g.test.cpp
• test_atcoder/agc013e.test.cpp
• test_atcoder/agc058d.test.cpp
• test_atcoder/agc058d2.test.cpp
• test_atcoder/arc133f.test.cpp
• test_atcoder/arc153f.test.cpp
• test_atcoder/arc154f.test.cpp
• test_atcoder/arc160d.test.cpp
• test_atcoder/arc162f.test.cpp

Code

#pragma once

constexpr u32 mod_pow_constexpr(u64 a, u64 n, u32 mod) {
  a %= mod;
  u64 res = 1;
  FOR(32) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod, n /= 2;
  }
  return res;
}

template <typename T, u32 p0, u32 p1>
T CRT2(u64 a0, u64 a1) {
  static_assert(p0 < p1);
  static constexpr u64 x0_1 = mod_pow_constexpr(p0, p1 - 2, p1);
  u64 c = (a1 - a0 + p1) * x0_1 % p1;
  return a0 + c * p0;
}

template <typename T, u32 p0, u32 p1, u32 p2>
T CRT3(u64 a0, u64 a1, u64 a2) {
  static_assert(p0 < p1 && p1 < p2);
  static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1);
  static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
  static constexpr u64 p01 = u64(p0) * p1;
  u64 c = (a1 - a0 + p1) * x1 % p1;
  u64 ans_1 = a0 + c * p0;
  c = (a2 - ans_1 % p2 + p2) * x2 % p2;
  return T(ans_1) + T(c) * T(p01);
}

template <typename T, u32 p0, u32 p1, u32 p2, u32 p3, u32 p4>
T CRT5(u64 a0, u64 a1, u64 a2, u64 a3, u64 a4) {
  static_assert(p0 < p1 && p1 < p2 && p2 < p3 && p3 < p4);
  static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1);
  static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
  static constexpr u64 x3
      = mod_pow_constexpr(u64(p0) * p1 % p3 * p2 % p3, p3 - 2, p3);
  static constexpr u64 x4
      = mod_pow_constexpr(u64(p0) * p1 % p4 * p2 % p4 * p3 % p4, p4 - 2, p4);
  static constexpr u64 p01 = u64(p0) * p1;
  static constexpr u64 p23 = u64(p2) * p3;
  u64 c = (a1 - a0 + p1) * x1 % p1;
  u64 ans_1 = a0 + c * p0;
  c = (a2 - ans_1 % p2 + p2) * x2 % p2;
  u128 ans_2 = ans_1 + c * static_cast<u128>(p01);
  c = static_cast<u64>(a3 - ans_2 % p3 + p3) * x3 % p3;
  u128 ans_3 = ans_2 + static_cast<u128>(c * p2) * p01;
  c = static_cast<u64>(a4 - ans_3 % p4 + p4) * x4 % p4;
  return T(ans_3) + T(c) * T(p01) * T(p23);
}

#line 2 "mod/crt3.hpp"

constexpr u32 mod_pow_constexpr(u64 a, u64 n, u32 mod) {
  a %= mod;
  u64 res = 1;
  FOR(32) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod, n /= 2;
  }
  return res;
}

template <typename T, u32 p0, u32 p1>
T CRT2(u64 a0, u64 a1) {
  static_assert(p0 < p1);
  static constexpr u64 x0_1 = mod_pow_constexpr(p0, p1 - 2, p1);
  u64 c = (a1 - a0 + p1) * x0_1 % p1;
  return a0 + c * p0;
}

template <typename T, u32 p0, u32 p1, u32 p2>
T CRT3(u64 a0, u64 a1, u64 a2) {
  static_assert(p0 < p1 && p1 < p2);
  static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1);
  static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
  static constexpr u64 p01 = u64(p0) * p1;
  u64 c = (a1 - a0 + p1) * x1 % p1;
  u64 ans_1 = a0 + c * p0;
  c = (a2 - ans_1 % p2 + p2) * x2 % p2;
  return T(ans_1) + T(c) * T(p01);
}

template <typename T, u32 p0, u32 p1, u32 p2, u32 p3, u32 p4>
T CRT5(u64 a0, u64 a1, u64 a2, u64 a3, u64 a4) {
  static_assert(p0 < p1 && p1 < p2 && p2 < p3 && p3 < p4);
  static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1);
  static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
  static constexpr u64 x3
      = mod_pow_constexpr(u64(p0) * p1 % p3 * p2 % p3, p3 - 2, p3);
  static constexpr u64 x4
      = mod_pow_constexpr(u64(p0) * p1 % p4 * p2 % p4 * p3 % p4, p4 - 2, p4);
  static constexpr u64 p01 = u64(p0) * p1;
  static constexpr u64 p23 = u64(p2) * p3;
  u64 c = (a1 - a0 + p1) * x1 % p1;
  u64 ans_1 = a0 + c * p0;
  c = (a2 - ans_1 % p2 + p2) * x2 % p2;
  u128 ans_2 = ans_1 + c * static_cast<u128>(p01);
  c = static_cast<u64>(a3 - ans_2 % p3 + p3) * x3 % p3;
  u128 ans_3 = ans_2 + static_cast<u128>(c * p2) * p01;
  c = static_cast<u64>(a4 - ans_3 % p4 + p4) * x4 % p4;
  return T(ans_3) + T(c) * T(p01) * T(p23);
}

Back to top page