Module: Extended Euclid's Algorithm


Problem

2 /2


Diophantine equations

Problem

Natural numbers a, b, c are given. If the equation \(ax+by=c\) has solutions in integers, then choose the solution in which the number x has the smallest non-negative value and output this solution (two numbers x and y separated one space). If there is no solution, then print the word Impossible.

Input 
Three natural numbers are entered.

Imprint
Print the answer to the problem.

Note
The complexity of the algorithm must be equal to the complexity of the Euclidean algorithm + a constant.
 
Examples
# Input Output
1 1 2 3 1 1
2 10 6 8 2 -2

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!