2025-01-09 01:45:09 +03:00
|
|
|
import re, sys
|
|
|
|
|
|
|
|
def gcd(a, b):
|
|
|
|
while b != 0:
|
|
|
|
b, a = a % b, b
|
|
|
|
return a
|
|
|
|
|
|
|
|
def get_q_list(m, a):
|
|
|
|
l = []
|
|
|
|
while a:
|
|
|
|
r, q = m % a, m // a
|
|
|
|
m, a = a, r
|
|
|
|
l.append(q)
|
|
|
|
return l
|
|
|
|
|
|
|
|
def get_p_n(n, q_list):
|
|
|
|
if n == 0:
|
|
|
|
return q_list[0]
|
|
|
|
if n == 1:
|
|
|
|
return q_list[0] * q_list[1] + 1
|
|
|
|
return q_list[n] * get_p_n(n - 1, q_list) + get_p_n(n - 2, q_list)
|
|
|
|
|
|
|
|
def get_x0(a, b, m):
|
|
|
|
q_list = get_q_list(m, a)
|
|
|
|
n = len(q_list) - 1
|
2025-01-09 02:00:19 +03:00
|
|
|
p = get_p_n(n-1, get_q_list(m, a))
|
|
|
|
x0 = ((-1)**n*p*b)%m
|
|
|
|
return x0
|
2025-01-09 01:45:09 +03:00
|
|
|
|
|
|
|
def solve(task):
|
|
|
|
f = re.fullmatch(r'(\d+)x=(\d+)mod(\d+)', task)
|
|
|
|
if f == None:
|
|
|
|
return "Usage Example: py chain_fraction.py '7x=8mod13'"
|
|
|
|
a, b, m = int(f.groups()[0]), int(f.groups()[1]), int(f.groups()[2])
|
2025-01-09 02:00:19 +03:00
|
|
|
d = gcd(a, m)
|
2025-01-09 01:45:09 +03:00
|
|
|
if d > 1 and b % d != 0:
|
|
|
|
return 'No solutions'
|
2025-01-09 02:00:19 +03:00
|
|
|
a1, b1, m1 = a // d, b // d, m // d
|
|
|
|
x0 = get_x0(a1, b1, m1)
|
|
|
|
s = ""
|
|
|
|
for i in range(d):
|
|
|
|
s += f'x={(x0+m//d*i)%m}mod{m}\n'
|
|
|
|
return s[:-1]
|
2025-01-09 01:45:09 +03:00
|
|
|
|
|
|
|
if __name__ == "__main__":
|
|
|
|
if len(sys.argv) != 2:
|
|
|
|
print("Usage Example: py chain_fraction.py '7x=8mod13'")
|
|
|
|
sys.exit(1)
|
|
|
|
print(solve(sys.argv[1]))
|