mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

binary_gcd
(math/binary_gcd.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "math/binary_gcd.hpp"

binary_gcd

使い方

binary_gcd(ll a, ll b) : $\text{gcd}(a, b)$ を返す。$O(\log{a+b})$ 程度

概要

除算が遅いため、それを回避するためにビットシフトに限定した GCD 計算アルゴリズム

Verified with

• verify/yukicoder/1250.test.cpp
• verify/yukicoder/3020.test.cpp

Code

#pragma once

#include<algorithm>
#include<cmath>

long long binary_gcd(long long a, long long b){
	if(a == 0)return b;
	if(b == 0)return a;

	a = std::abs(a);
	b = std::abs(b);

	int a_zero = __builtin_ctzll(a);
	int b_zero = __builtin_ctzll(b);
	a >>= a_zero;
	b >>= b_zero;
	
	while(a != b){
		if(a > b){
			std::swap(a, b);
		}
		b -= a;
		b >>= __builtin_ctzll(b);
	}
	return a << std::min(a_zero, b_zero);
}

#line 2 "math/binary_gcd.hpp"

#include<algorithm>
#include<cmath>

long long binary_gcd(long long a, long long b){
	if(a == 0)return b;
	if(b == 0)return a;

	a = std::abs(a);
	b = std::abs(b);

	int a_zero = __builtin_ctzll(a);
	int b_zero = __builtin_ctzll(b);
	a >>= a_zero;
	b >>= b_zero;
	
	while(a != b){
		if(a > b){
			std::swap(a, b);
		}
		b -= a;
		b >>= __builtin_ctzll(b);
	}
	return a << std::min(a_zero, b_zero);
}

Back to top page