@staticmethod<EOL><INDENT>def diop_natural_solution_linear(c, a, b):<DEDENT>
def get_intersection(a, b, a_dir, b_dir):<EOL><INDENT>if (a_dir, b_dir) == ("<STR_LIT>", "<STR_LIT>"):<EOL><INDENT>lb = a if a > b else b<EOL>ub = float('<STR_LIT>')<EOL><DEDENT>elif (a_dir, b_dir) == ("<STR_LIT>", "<STR_LIT>"):<EOL><INDENT>if a > b:<EOL><INDENT>lb = b<EOL>ub = a<EOL><DEDENT>else:<EOL><INDENT>lb = None<EOL>ub = None<EOL><DEDENT><DEDENT>elif (a_dir, b_dir) == ("<STR_LIT>", "<STR_LIT>"):<EOL><INDENT>if b > a:<EOL><INDENT>lb = a<EOL>ub = b<EOL><DEDENT>else:<EOL><INDENT>lb = None<EOL>ub = None<EOL><DEDENT><DEDENT>elif (a_dir, b_dir) == ("<STR_LIT>", "<STR_LIT>"):<EOL><INDENT>ub = a if a < b else b<EOL>lb = float('<STR_LIT>')<EOL><DEDENT>return lb, ub<EOL><DEDENT>d = StridedInterval.igcd(a, StridedInterval.igcd(b, c))<EOL>a = a // d<EOL>b = b // d<EOL>c = c // d<EOL>if c == <NUM_LIT:0>:<EOL><INDENT>return (<NUM_LIT:0>, <NUM_LIT:0>)<EOL><DEDENT>else:<EOL><INDENT>x0, y0, d = StridedInterval.extended_euclid(int(abs(a)), int(abs(b)))<EOL>x0 = x0 * StridedInterval.sign(a)<EOL>y0 = y0 * StridedInterval.sign(b)<EOL>if c % d == <NUM_LIT:0>:<EOL><INDENT>"""<STR_LIT>"""<EOL>assert b != <NUM_LIT:0><EOL>assert a != <NUM_LIT:0><EOL>t0 = (-c * x0) / float(b)<EOL>t1 = (c * y0) / float(a)<EOL>if b < <NUM_LIT:0>:<EOL><INDENT>t0_dir = '<STR_LIT>'<EOL><DEDENT>else:<EOL><INDENT>t0_dir = '<STR_LIT>'<EOL><DEDENT>if a < <NUM_LIT:0>:<EOL><INDENT>t1_dir = '<STR_LIT>'<EOL><DEDENT>else:<EOL><INDENT>t1_dir = '<STR_LIT>'<EOL><DEDENT>lb, ub = get_intersection(t0, t1, t0_dir, t1_dir)<EOL>if lb <= <NUM_LIT:0> and ub >= <NUM_LIT:0>:<EOL><INDENT>t = ub if abs(ub) < abs(lb) else lb<EOL><DEDENT>elif lb == float('<STR_LIT>') or lb == float("<STR_LIT>"):<EOL><INDENT>t = ub<EOL><DEDENT>elif ub == float('<STR_LIT>') or ub == float("<STR_LIT>"):<EOL><INDENT>t = lb<EOL><DEDENT>else:<EOL><INDENT>t = ub if abs(ub) < abs(lb) else lb<EOL><DEDENT>if t == ub:<EOL><INDENT>t = int(math.floor(t))<EOL><DEDENT>else:<EOL><INDENT>t = int(math.ceil(t))<EOL><DEDENT>return (c*x0 + b*t, c*y0 - a*t)<EOL><DEDENT>else:<EOL><INDENT>return (None, None)<EOL><DEDENT><DEDENT>
It finds the fist natural solution of the diophantine equation
a*x + b*y = c. Some lines of this code are taken from the project
sympy.

:param c: constant
:param a: quotient of x
:param b: quotient of y
:return: the first natural solution of the diophatine equation