一次不定方程式

再帰を使わない版

code: python

# 拡張ユークリッドの互除法

# ax + by = 1 の特殊解（1つの解）を返す．a, b: 正の整数で，互いに素

def ex_euclid(a, b):

c, d, e, f = 1, 0, 0, 1

while b != 0:

c, d = d, c - a // b * d

e, f = f, e - a // b * f

a, b = b, a % b

return c, e

# 使用例

print(f'3x + 5y = 1 の特殊解は(x, y) = {ex_euclid(3, 5)}') # 3x2 + 5x(-1) = 1

print(f'90x + 37y = 1 の特殊解は(x, y) = {ex_euclid(90, 37)}') # 90x7 + 37x(-17) = 1

拡張ユークリッドの互除法を使う

code: python

# 拡張ユークリッドの互除法

# ax + by = 1 の特殊解（1つの解）を返す．a, b: 正の整数で，互いに素

def ex_euclid(a, b):

c, d, e, f = 1, 0, 0, 1

while b != 0:

c, d = d, c - a // b * d

e, f = f, e - a // b * f

a, b = b, a % b

return c, e

# 不定方程式 ax + by = c の解を1つ返す．a, b, c: 整数（負でも0でもOK）

# 解が存在しないときは None を返す

import math

def indet_liner_eq(a, b, c):

def sub(a, b, c): # a, b, c: 非負整数

if a == 0: # a=0の処理

if b == 0:

return (0, 0) if c == 0 else None

else:

return (0, c // b) if c % b == 0 else None

if b == 0: # b=0の処理

return (c // a, 0) if c % a == 0 else None

if c == 0: # a=0の処理

return 0, 0

# a, b, c: 正の整数

g = math.gcd(a, b)

if c % g > 0:

return None

aa, bb, cc = a // g, b // g, c // g # a, b: 互いに素

x, y = ex_euclid(aa, bb) # aax + bby = 1 の特殊解

return x * cc, y * cc

aa, bb, cc = abs(a), abs(b), abs(c) # aa, bb, cc: 非負整数

sgn_a = 1 if a >= 0 else -1

sgn_b = 1 if b >= 0 else -1

sgn_c = 1 if c >= 0 else -1

ans = sub(aa, bb, cc)

if ans is None:

return None

# 使用例

print(f'3x + 5y = 4 の特殊解は(x, y) = {indet_liner_eq(3, 5, 4)}') # 3x8 + 5x(-4) = 4

print(f'90x + 37y = 4 の特殊解は(x, y) = {indet_liner_eq(90, 37, 4)}') # 90x28 + 37x(-68) = 4

print(f'32x + 12y = 4 の特殊解は(x, y) = {indet_liner_eq(32, 12, 4)}') # 32x(-1) + 12x3 = 4

print(f'-32x + 12y = 4 の特殊解は(x, y) = {indet_liner_eq(-32, 12, 4)}') # -32x1 + 12x3 = 4

print(f'32x + 12y = -4 の特殊解は(x, y) = {indet_liner_eq(32, 12, -4)}') # 32x1 + 12x(-3) = -4

print(f'32x + 12y = 10 の特殊解は(x, y) = {indet_liner_eq(32, 12, 10)}') # 32x + 12y = 10を満たす(x,y)は存在しない

print(f'0x + 4y = -12 の特殊解は(x, y) = {indet_liner_eq(0, 4, -4)}') # 0x0 + 4x(-3) = -12

print(f'0x + 0y = 4 の特殊解は(x, y) = {indet_liner_eq(0, 0, 4)}') # 0x + 0y = 4を満たす解は存在しない