test/extGcd.test.cpp

• View this file on GitHub
• Last update: 2021-03-07 15:45:48+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/all/NTL_1_E

Depends on

• math/extGcd.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/all/NTL_1_E"
#include "./../math/extGcd.cpp"
#include <iostream>
using namespace std;

int main() {
	long long x, y;
	cin >> x >> y;
	long long a, b;
	extGcd(x, y, a, b);
	cout << a << ' ' << b << '\n';
}

#line 1 "test/extGcd.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/all/NTL_1_E"
#line 2 "math/extGcd.cpp"
#include <tuple>

template <class T> T extGcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extGcd(b, a % b, y, x);
		y -= (a / b) * x;
	} else {
		x = 1;
		y = 0;
	}
	return d;
}

template <class T> std::tuple<T, T, T> extGcd(T a, T b) {
	T x, y;
	T gcd = extGcd(a, b, x, y);
	return {gcd, x, y};
}
#line 3 "test/extGcd.test.cpp"
#include <iostream>
using namespace std;

int main() {
	long long x, y;
	cin >> x >> y;
	long long a, b;
	extGcd(x, y, a, b);
	cout << a << ' ' << b << '\n';
}

Back to top page