test/math/extended_gcd/aoj_ntl_1_e.test.cpp

• View this file on GitHub
• Last update: 2023-09-06 15:21:24+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E

Depends on

• 拡張ユークリッドの互除法 (src/math/extended_gcd.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E

#include "src/math/extended_gcd.hpp"

#include <iostream>

using namespace std;

int main() {
	int a, b, x, y;
	cin >> a >> b;
	extended_gcd(a, b, x, y);
	cout << x << " " << y << endl;

	return 0;
}

#line 1 "test/math/extended_gcd/aoj_ntl_1_e.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E

#line 1 "src/math/extended_gcd.hpp"



template<class T>
T extended_gcd(T a, T b, T &x, T &y) { // ax+by=gcd(a,b)
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	T d = extended_gcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

template<class T>
T modinv(T a, T mod) { // a,modは互いに素
	T x, y;
	extended_gcd(a, mod, x, y);
	return (x % mod + mod) % mod;
}


#line 4 "test/math/extended_gcd/aoj_ntl_1_e.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int a, b, x, y;
	cin >> a >> b;
	extended_gcd(a, b, x, y);
	cout << x << " " << y << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	13 ms	7 MB
g++	00_sample_01.in	AC	12 ms	7 MB
g++	01_small_00.in	AC	12 ms	7 MB
g++	01_small_01.in	AC	12 ms	7 MB
g++	01_small_02.in	AC	12 ms	7 MB
g++	01_small_03.in	AC	12 ms	7 MB
g++	01_small_04.in	AC	12 ms	7 MB
g++	01_small_05.in	AC	12 ms	7 MB
g++	02_critical_00.in	AC	12 ms	7 MB
g++	02_critical_01.in	AC	12 ms	7 MB
g++	02_critical_02.in	AC	12 ms	7 MB
g++	02_critical_03.in	AC	12 ms	7 MB
g++	03_large_00.in	AC	12 ms	7 MB
g++	03_large_01.in	AC	12 ms	7 MB
g++	03_large_02.in	AC	12 ms	7 MB
g++	03_large_03.in	AC	12 ms	7 MB
g++	03_large_04.in	AC	12 ms	7 MB
g++	03_large_05.in	AC	12 ms	7 MB
g++	03_large_06.in	AC	12 ms	7 MB
g++	03_large_07.in	AC	12 ms	7 MB
g++	03_large_08.in	AC	12 ms	7 MB
g++	03_large_09.in	AC	12 ms	7 MB
g++	04_corner_00.in	AC	12 ms	7 MB
g++	04_corner_01.in	AC	11 ms	7 MB
g++	04_corner_02.in	AC	12 ms	7 MB
g++	04_corner_03.in	AC	12 ms	7 MB
g++	05_rand_00.in	AC	12 ms	7 MB
g++	05_rand_01.in	AC	12 ms	7 MB
g++	05_rand_02.in	AC	12 ms	7 MB
g++	05_rand_03.in	AC	12 ms	7 MB
g++	05_rand_04.in	AC	12 ms	7 MB
g++	05_rand_05.in	AC	12 ms	7 MB
clang++	00_sample_00.in	AC	11 ms	11 MB
clang++	00_sample_01.in	AC	11 ms	13 MB
clang++	01_small_00.in	AC	11 ms	11 MB
clang++	01_small_01.in	AC	12 ms	13 MB
clang++	01_small_02.in	AC	11 ms	9 MB
clang++	01_small_03.in	AC	11 ms	15 MB
clang++	01_small_04.in	AC	12 ms	15 MB
clang++	01_small_05.in	AC	11 ms	9 MB
clang++	02_critical_00.in	AC	12 ms	15 MB
clang++	02_critical_01.in	AC	12 ms	15 MB
clang++	02_critical_02.in	AC	12 ms	13 MB
clang++	02_critical_03.in	AC	11 ms	7 MB
clang++	03_large_00.in	AC	11 ms	15 MB
clang++	03_large_01.in	AC	11 ms	7 MB
clang++	03_large_02.in	AC	11 ms	11 MB
clang++	03_large_03.in	AC	12 ms	15 MB
clang++	03_large_04.in	AC	12 ms	15 MB
clang++	03_large_05.in	AC	12 ms	15 MB
clang++	03_large_06.in	AC	11 ms	9 MB
clang++	03_large_07.in	AC	11 ms	9 MB
clang++	03_large_08.in	AC	11 ms	9 MB
clang++	03_large_09.in	AC	11 ms	7 MB
clang++	04_corner_00.in	AC	12 ms	15 MB
clang++	04_corner_01.in	AC	12 ms	13 MB
clang++	04_corner_02.in	AC	12 ms	13 MB
clang++	04_corner_03.in	AC	12 ms	9 MB
clang++	05_rand_00.in	AC	12 ms	15 MB
clang++	05_rand_01.in	AC	12 ms	13 MB
clang++	05_rand_02.in	AC	11 ms	9 MB
clang++	05_rand_03.in	AC	11 ms	11 MB
clang++	05_rand_04.in	AC	11 ms	11 MB
clang++	05_rand_05.in	AC	11 ms	9 MB

Back to top page