10104 - Euclid Problem ~ Ankur's Blog

Resources

	///Extended Euclidean Algorithm
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;

	ll Extended_gcd(ll a, ll b, ll &x, ll &y)
	{
	if(a == 0)
	{
	x = 0;
	y = 1;
	return b;
	}
	ll x1, y1;
	ll d = Extended_gcd(b % a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
	}

	ll Ex_gcd(ll a, ll b, ll &x, ll &y)
	{
	if(b == 0)
	{
	x = 1;
	y = 0;
	return a;
	}
	ll x1, y1;
	ll d = Ex_gcd(b, a % b, x1, y1);
	y = x1 - (a / b) * y1;
	x = y1;
	return d;
	}

	ll iterative_Ex_gcd(ll A, ll B, ll &X, ll &Y)
	{
	ll x, y, u, v, a, b, q, r, m, n;
	x = 0;
	y = 1;
	u = 1;
	v = 0;
	a = A;
	b = B;

	while(a != 0){
	q = b / a;
	r = b % a;
	b = a;
	a = r;

	m = x - (u * q);
	n = y - (v * q);
	x = u;
	y = v;
	u = m;
	v = n;
	}

	X = x;
	Y = y;
	return b;
	}

	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/

	ll a, b;
	while(cin >> a >> b)
	{
	ll x, y;
	ll gcd = Ex_gcd(a, b, x, y);
	//ll gcd = iterative_Ex_gcd(a,b, x, y);
	cout << x << " " << y << " " << gcd << endl;
	}


	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);

	return 0;
	}

view raw Ex_gcd.cpp hosted with ❤ by GitHub

Ankur's Blog