cp_library/math/ext_gcd_fn.py

• View this file on GitHub
• Last update: 2025-08-24 20:27:05+09:00

Verified with

• test/atcoder/abc/abc186_e_gcd_ex.test.py

Code

import cp_library.__header__
import cp_library.math.__header__

def ext_gcd(a, b):
    ''' Returns (x, y, d) where: ax + by = d = gcd(a,b) '''
    if a and b:
        x, y, r, s = 1, 0, 0, 1
        while b: q, c = divmod(a,b); a, b, r, s, x, y = b, c, x - q*r, y - q*s, r, s
        return x, y, a
    elif a: return 1, 0, a
    elif b: return 0, 1, b
    else: return 0, 1, 0

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


def ext_gcd(a, b):
    ''' Returns (x, y, d) where: ax + by = d = gcd(a,b) '''
    if a and b:
        x, y, r, s = 1, 0, 0, 1
        while b: q, c = divmod(a,b); a, b, r, s, x, y = b, c, x - q*r, y - q*s, r, s
        return x, y, a
    elif a: return 1, 0, a
    elif b: return 0, 1, b
    else: return 0, 1, 0

Back to top page