Created
March 19, 2016 13:43
-
-
Save Newlifer/fbfd7742b5bb82194c2d to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // MCCME issue 3299 | |
| #include <iostream> | |
| #include <tuple> | |
| auto gcd (int a, int b) -> std::tuple<int, int, int> // <GCD, x, y> | |
| { | |
| if (a == 0) | |
| { | |
| return std::make_tuple (b, 0, 1); | |
| } | |
| else | |
| { | |
| const auto rs = gcd (b % a, a); | |
| const int d = std::get<0> (rs); | |
| const int x1 = std::get<1> (rs); | |
| const int y1 = std::get<2> (rs); | |
| const int x = y1 - int (b / a) * x1; | |
| const int y = x1; | |
| return std::make_tuple (d, x, y); | |
| } | |
| } | |
| auto main () -> int | |
| { | |
| int a, b, c; | |
| std::cin >> a >> b >> c; | |
| if (a == 0 && b == 0 && c != 0) | |
| { | |
| std::cout << "Impossible" << std::endl; | |
| return 0; | |
| } | |
| const auto rs = gcd (a, b); | |
| if (c % std::get<0> (rs) != 0) | |
| { | |
| std::cout << "Impossible" << std::endl; | |
| } | |
| else | |
| { | |
| std::cout << std::get<0> (rs) << " " | |
| << std::get<1> (rs) << " " | |
| << std::get<2> (rs) << | |
| std::endl; | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment