library/test/aoj/NTL_1_E-Extended_Euclid_Algorithm.test.cpp

• View this file on GitHub
• Last update: 2024-03-15 16:42:38+06:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E

Depends on

• Extgcd (extended Euclidean algorithm) (library/math/extgcd.hpp)

Code

#include <bits/stdc++.h>
using namespace std;
#include "../../math/extgcd.hpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E"

int main() {
    ios_base::sync_with_stdio(0);
    int a, b, x, y;
    cin>>a>>b;
    extgcd(a, b, x, y);
    cout<<x<<" "<<y<<'\n';
    return 0;
}

#line 1 "library/test/aoj/NTL_1_E-Extended_Euclid_Algorithm.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#line 1 "library/math/extgcd.hpp"
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;
}
#line 4 "library/test/aoj/NTL_1_E-Extended_Euclid_Algorithm.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E"

int main() {
    ios_base::sync_with_stdio(0);
    int a, b, x, y;
    cin>>a>>b;
    extgcd(a, b, x, y);
    cout<<x<<" "<<y<<'\n';
    return 0;
}

Test cases

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

Back to top page