Skip to content

Instantly share code, notes, and snippets.

@Newlifer
Created March 19, 2016 13:43
Show Gist options
  • Select an option

  • Save Newlifer/fbfd7742b5bb82194c2d to your computer and use it in GitHub Desktop.

Select an option

Save Newlifer/fbfd7742b5bb82194c2d to your computer and use it in GitHub Desktop.
// 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