cp_library/math/nt/mod_inv_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Required by

• cp_library/math/conv/conv_int_fn.py
• cp_library/math/fps/fps_exp_fn.py
• cp_library/math/fps/fps_ideriv_k_fn.py
• cp_library/math/fps/fps_inv_fn.py
• cp_library/math/fps/fps_log_fn.py
• cp_library/math/fps/fps_pow_fn.py
• cp_library/math/fps/fps_tayler_shift_fn.py
• cp_library/math/mod/mint_ntt_cls.py
• cp_library/math/nt/chinese_remainder_theorem_fn.py
• cp_library/math/nt/ntt_cls.py
• cp_library/math/series/mod/geosum_fn.py
• cp_library/math/table/modcomb_cls.py
• cp_library/math/table/stirling1_k_fn.py
• cp_library/math/table/stirling1_n_fn.py
• cp_library/math/table/stirling2_k_fn.py
• cp_library/math/table/stirling2_n_fn.py

Verified with

• test/atcoder/arc/arc168_c_swap_characters_combinatoric.test.py
• test/library-checker/convolution/convolution.test.py
• test/library-checker/convolution/convolution_int.test.py
• test/library-checker/convolution/convolution_mod_1000000007.test.py
• test/library-checker/enumerative-combinatorics/stirling_number_of_the_first_kind.test.py
• test/library-checker/enumerative-combinatorics/stirling_number_of_the_first_kind_fixed_k.test.py
• test/library-checker/enumerative-combinatorics/stirling_number_of_the_second_kind.test.py
• test/library-checker/enumerative-combinatorics/stirling_number_of_the_second_kind_fixed_k.test.py
• test/library-checker/polynomial/exp_of_formal_power_series.test.py
• test/library-checker/polynomial/inv_of_formal_power_series.test.py
• test/library-checker/polynomial/log_of_formal_power_series.test.py
• test/library-checker/polynomial/polynomial_taylor_shift.test.py
• test/library-checker/polynomial/pow_of_formal_power_series.test.py

Code

import cp_library.math.nt.__header__

def mod_inv(x, mod):
    a,b,s,t = x, mod, 1, 0
    while b:
        a,b,s,t = b,a%b,t,s-a//b*t
    if a == 1: return s % mod
    raise ValueError(f"{x} is not invertible in mod {mod}")

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def mod_inv(x, mod):
    a,b,s,t = x, mod, 1, 0
    while b:
        a,b,s,t = b,a%b,t,s-a//b*t
    if a == 1: return s % mod
    raise ValueError(f"{x} is not invertible in mod {mod}")

Back to top page