test/aoj/NTL_1_E.test.cpp

View this file on GitHub
Last update: 2021-06-20 16:57:30+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E

Depends on

math/extgcd.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../math/extgcd.cpp"
#undef call_from_test

signed main(){
  int a,b;
  cin>>a>>b;
  auto[x,y]=extgcd(a,b);
  cout<<x<<" "<<y<<endl;
  return 0;
}

#line 1 "test/aoj/NTL_1_E.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "math/extgcd.cpp"

#line 3 "math/extgcd.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// find (x, y) s.t. ax + by = gcd(a, b), minimize |x| + |y|
// |x| <= b, |y| <= a
// return gcd(a, b)
template<typename 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<typename T>
pair<T, T> extgcd(T a,T b){
  T x,y;
  extgcd(a,b,x,y);
  return make_pair(x,y);
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 8 "test/aoj/NTL_1_E.test.cpp"
#undef call_from_test

signed main(){
  int a,b;
  cin>>a>>b;
  auto[x,y]=extgcd(a,b);
  cout<<x<<" "<<y<<endl;
  return 0;
}