test/math/BinaryGCD.test.cpp

View this file on GitHub
Last update: 2024-06-01 01:21:46+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"
using u64 = uint64_t;
#include "src/math/BinaryGCD.hpp"

int main() {
   mt19937_64 rnd;
   rep(shift, 0, 64) {
      rep(i, 0, (ll)1e5) {
         u64 a = rnd() >> shift, b = rnd() >> shift;
         assert(gcd(a, b) == binary_gcd(a, b));
      }
   }
   puts("Hello World");
}

#line 1 "test/math/BinaryGCD.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 3 "test/math/BinaryGCD.test.cpp"
using u64 = uint64_t;
#line 1 "src/math/BinaryGCD.hpp"
u64 ctz(u64 x) { return countr_zero(x); }
u64 binary_gcd(u64 x, u64 y) {
   if(!x || !y) return x | y;
   u64 n = ctz(x), m = ctz(y);
   x >>= n, y >>= m;
   while(x != y) {
      if(x > y) x = (x - y) >> ctz(x - y);
      else y = (y - x) >> ctz(y - x);
   }
   return x << min(n, m);
}
#line 5 "test/math/BinaryGCD.test.cpp"

int main() {
   mt19937_64 rnd;
   rep(shift, 0, 64) {
      rep(i, 0, (ll)1e5) {
         u64 a = rnd() >> shift, b = rnd() >> shift;
         assert(gcd(a, b) == binary_gcd(a, b));
      }
   }
   puts("Hello World");
}