mod/crt3.hpp

• View this file on GitHub
• Last update: 2023-11-01 03:36:04+09:00
• Include: #include "mod/crt3.hpp"

Required by

• bigint/base.hpp
• bigint/binary.hpp
• graph/characteristic_polynomial_of_tree_adjacency_matrix.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/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/multipoint.hpp
• poly/multivar_convolution.hpp
• poly/multivar_convolution_cyclic.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

Verified with

• 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/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/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_of_fps.test.cpp
• test/library_checker/polynomial/compositional_inverse.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/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/composition_1_minus_ex.test.cpp
• test/mytest/composition_ex_minus_1.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/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/slice_rational_fps.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/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/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/2649.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/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/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

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, u32 p2>
T CRT3(u64 a0, u64 a1, u64 a2) {
  static_assert(p0 < p1 && p1 < p2);
  static constexpr u64 x0_1 = mod_pow_constexpr(p0, p1 - 2, p1);
  static constexpr u64 x01_2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
  u64 c = (a1 - a0 + p1) * x0_1 % p1;
  u64 a = a0 + c * p0;
  c = (a2 - a % p2 + p2) * x01_2 % p2;
  return T(a) + T(c) * T(p0) * T(p1);
}

#line 1 "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, u32 p2>
T CRT3(u64 a0, u64 a1, u64 a2) {
  static_assert(p0 < p1 && p1 < p2);
  static constexpr u64 x0_1 = mod_pow_constexpr(p0, p1 - 2, p1);
  static constexpr u64 x01_2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
  u64 c = (a1 - a0 + p1) * x0_1 % p1;
  u64 a = a0 + c * p0;
  c = (a2 - a % p2 + p2) * x01_2 % p2;
  return T(a) + T(c) * T(p0) * T(p1);
}

Back to top page