test/math/ExtGCD.test.cpp

View this file on GitHub
Last update: 2024-06-01 10:05:24+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include "test/template.hpp"
#include "src/math/ExtGCD.hpp"

using i128 = __int128_t;
i128 abs(i128 x) { return x < 0 ? -x : x; }
int main() {
   mt19937_64 rnd;
   rep(shift, 1, 64) {
      rep(i, 0, (ll)5e4) {
         ll a = rnd() >> shift;
         ll b = rnd() >> shift;
         const ll g = gcd(a, b);
         ll x, y;
         assert(extgcd(a, b, x, y) == g);
         assert((i128)a * x + (i128)b * y == g);
         if(g) {
            assert(abs((i128)x) + abs((i128)y) <= abs((i128)x - b / g) + abs((i128)y + a / g));
            assert(abs((i128)x) + abs((i128)y) <= abs((i128)x + b / g) + abs((i128)y - a / g));
         }
      }
   }
   puts("Hello World");
}

#line 1 "test/math/ExtGCD.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 1 "src/math/ExtGCD.hpp"
// returns gcd(a, b) and assign x, y to integers
// s.t. ax + by = gcd(a, b) and |x| + |y| is minimized
ll extgcd(ll a, ll b, ll& x, ll& y) {
   // assert(a >= 0 && b >= 0);
   if(!b) return x = 1, y = 0, a;
   ll d = extgcd(b, a % b, y, x);
   y -= a / b * x;
   return d;
}
#line 4 "test/math/ExtGCD.test.cpp"

using i128 = __int128_t;
i128 abs(i128 x) { return x < 0 ? -x : x; }
int main() {
   mt19937_64 rnd;
   rep(shift, 1, 64) {
      rep(i, 0, (ll)5e4) {
         ll a = rnd() >> shift;
         ll b = rnd() >> shift;
         const ll g = gcd(a, b);
         ll x, y;
         assert(extgcd(a, b, x, y) == g);
         assert((i128)a * x + (i128)b * y == g);
         if(g) {
            assert(abs((i128)x) + abs((i128)y) <= abs((i128)x - b / g) + abs((i128)y + a / g));
            assert(abs((i128)x) + abs((i128)y) <= abs((i128)x + b / g) + abs((i128)y - a / g));
         }
      }
   }
   puts("Hello World");
}