test/extGCD.test.cpp

• View this file on GitHub
• Last update: 2024-02-10 23:01:10+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E&lang=ja

Depends on

• math/extGCD.hpp

Code

#define PROBLEM   "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E&lang=ja"
#include "../math/extGCD.hpp"

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

using ll=long long;

int main() {
    ll a,b;cin>>a>>b;
    
auto p=extgcd(a,b);
cout<<p.first<<" "<<p.second<<endl;
}

#line 1 "test/extGCD.test.cpp"
#define PROBLEM   "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E&lang=ja"
#line 2 "math/extGCD.hpp"
#include<bits/stdc++.h>
using namespace std;

pair<long long, long long> extgcd(long long a, long long b) {
  if (b == 0) return make_pair(1, 0);
  long long x, y;
  tie(y, x) = extgcd(b, a % b);
  y -= a / b * x;
  return make_pair(x, y);
}

#line 3 "test/extGCD.test.cpp"

#line 5 "test/extGCD.test.cpp"
using namespace std;

using ll=long long;

int main() {
    ll a,b;cin>>a>>b;
    
auto p=extgcd(a,b);
cout<<p.first<<" "<<p.second<<endl;
}

Back to top page