Skip to content

Instantly share code, notes, and snippets.

@Chillee

Chillee/egcd.cpp

Last active April 13, 2019 04:18
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Chillee/569a91b7c5eb7a111cd84353017c362b to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Chillee/569a91b7c5eb7a111cd84353017c362b to your computer and use it in GitHub Desktop.
Download ZIP
Extended Euclidean Algorithm
Raw
egcd.cpp
ll euclid(ll a, ll b, ll &x, ll &y) {
if (b) {
ll d = euclid(b, a % b, y, x);
return y -= a / b * x, d;
}
return x = 1, y = 0, a;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment