cp_library/math/series/mod/geosum_fn.py

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

Depends on

• cp_library/math/nt/mod_inv_fn.py

Code

import cp_library.math.series.mod.__header__
from cp_library.math.nt.mod_inv_fn import mod_inv

def geosum(a, r, n, mod):
    if r == 1: return a*n
    return a*(pow(r,n,mod)-1)%mod*mod_inv(r-1, 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}")

def geosum(a, r, n, mod):
    if r == 1: return a*n
    return a*(pow(r,n,mod)-1)%mod*mod_inv(r-1, mod)%mod

Back to top page