algorithm-dev
This documentation is automatically generated by online-judge-tools/verification-helper
algorithm/Math/NumberTheory/bigint_utils.hpp
- View this file on GitHub
- Last update: 2025-07-03 00:41:25+09:00
- Include:
#include "algorithm/Math/NumberTheory/bigint_utils.hpp"
Depends on
多倍長整数
(algorithm/Math/NumberTheory/bigint.hpp)
- 多倍長整数（16進数）
(algorithm/Math/NumberTheory/binary_bigint.hpp)
Code
#ifndef ALGORITHM_BIGINT_UTILS_HPP
#define ALGORITHM_BIGINT_UTILS_HPP 1
#include "bigint.hpp"
#include "binary_bigint.hpp"
namespace algorithm {
BinaryBigint dtoh(const Bigint &a) {
BinaryBigint res;
for(auto iter = a.words().crbegin(); iter < a.words().crend(); ++iter) {
res *= Bigint::base();
res += *iter;
}
if(a.is_negative()) res.negate();
return res;
};
Bigint htod(const BinaryBigint &a) {
if(a.is_negative()) return htod(-a).negate();
Bigint res;
for(auto iter = a.words().crbegin(); iter < a.words().crend(); ++iter) {
res *= BinaryBigint::base();
res += *iter;
}
return res;
};
} // namespace algorithm
#endif#line 1 "algorithm/Math/NumberTheory/bigint_utils.hpp"
#line 1 "algorithm/Math/NumberTheory/bigint.hpp"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <sstream>
#include <string>
#include <string_view>
#include <utility>
#include <vector>
namespace algorithm {
// 多倍長整数．
class Bigint {
static constexpr int32_t BASE = 1'000'000'000;
static constexpr size_t BASE_DIGIT = 9;
std::vector<int32_t> m_words;
bool m_neg;
explicit Bigint(const std::vector<int32_t> &words, bool neg) : m_words(words), m_neg(neg) {}
explicit Bigint(std::vector<int32_t> &&words, bool neg) : m_words(std::move(words)), m_neg(neg) {}
static constexpr bool isdigit(char c) { return '0' <= c and c <= '9'; }
static constexpr bool validate(std::string_view sv, size_t n) {
if(n == 0) return false;
if(sv[0] == '+' or sv[0] == '-') return validate_unsigned(sv.substr(1), n - 1);
return validate_unsigned(sv, n);
}
static constexpr bool validate_unsigned(std::string_view sv, size_t n) {
if(n == 0) return false;
return std::find_if_not(sv.cbegin(), sv.cend(), [](char c) -> bool { return isdigit(c); }) == sv.cend();
}
static int compare(const Bigint &lhs, const Bigint &rhs) {
if(lhs.m_neg ^ rhs.m_neg) return (lhs.m_neg ? -1 : 1);
return compare(lhs.m_words, lhs.m_words.size(), rhs.m_words, rhs.m_words.size());
}
static int compare(const std::vector<int32_t> &lhs, ssize_t n, const std::vector<int32_t> &rhs, ssize_t m) {
if(n < m) return -1;
if(n > m) return 1;
for(ssize_t i = n - 1; i >= 0; --i) {
if(lhs[i] == rhs[i]) continue;
if(lhs[i] < rhs[i]) return -1;
return 1;
}
return 0;
}
static int32_t add_store(int32_t &word, int32_t val) {
if(val < 0) {
word = val + BASE;
return -1;
}
if(val < BASE) {
word = val;
return 0;
}
word = val - BASE;
return 1;
}
static int32_t store(int32_t &word, int64_t val) {
int32_t carry = val / BASE;
word = val - (int64_t)carry * BASE;
if(word < 0) word += BASE, --carry;
return carry;
}
static size_t shrink(std::vector<int32_t> &words) {
while(!words.empty() and words.back() == 0) words.pop_back();
return words.size();
}
static size_t zeroisation(std::vector<int32_t> &words) {
words.clear();
return 0;
}
static size_t negation(std::vector<int32_t> &words) {
int32_t ncarry = 0;
for(int32_t &word : words) ncarry = add_store(word, -word + ncarry);
return words.size();
}
static void addition(std::vector<int32_t> &lhs, size_t n, const std::vector<int32_t> &rhs, size_t m) {
n = std::max(n, m);
lhs.resize(n, 0);
int32_t carry = 0;
for(size_t i = 0; i < m; ++i) carry = add_store(lhs[i], lhs[i] + rhs[i] + carry);
for(size_t i = m; i < n and carry > 0; ++i) carry = add_store(lhs[i], lhs[i] + carry);
if(carry > 0) lhs.push_back(carry);
}
static bool subtraction(std::vector<int32_t> &lhs, size_t n, const std::vector<int32_t> &rhs, size_t m) {
n = std::max(n, m);
lhs.resize(n, 0);
int32_t ncarry = 0;
for(size_t i = 0; i < m; ++i) ncarry = add_store(lhs[i], lhs[i] - rhs[i] + ncarry);
for(size_t i = m; i < n and ncarry < 0; ++i) ncarry = add_store(lhs[i], lhs[i] + ncarry);
if(ncarry < 0) negation(lhs);
shrink(lhs);
return ncarry < 0;
}
static std::vector<int32_t> multiplication(const std::vector<int32_t> &lhs, size_t n, const std::vector<int32_t> &rhs, size_t m) {
std::vector<int32_t> res(n + m, 0);
for(size_t j = 0; j < m; ++j) {
if(rhs[j] == 0) continue;
int32_t carry = 0;
for(size_t i = 0; i < n; ++i) carry = store(res[i + j], res[i + j] + (int64_t)lhs[i] * rhs[j] + carry);
res[j + n] = carry;
}
shrink(res);
return res;
}
static std::vector<int32_t> division(std::vector<int32_t> &lhs, ssize_t n, const std::vector<int32_t> &rhs, ssize_t m) {
assert(m > 0);
if(n < m) return {};
std::vector<int32_t> res(n - m + 1);
auto bisearch = [&](ssize_t offset) -> int32_t {
if(n - offset < m) return 0;
auto eval = [&](int32_t d) -> bool {
int32_t ncarry = 0;
for(ssize_t i = 0; i < m; ++i) {
int32_t tmp;
ncarry = store(tmp, lhs[i + offset] - (int64_t)rhs[i] * d + ncarry);
}
int32_t last = (m + offset < n ? lhs[m + offset] : 0) + ncarry;
return last >= 0;
};
int32_t ok = 0, ng = BASE;
while(ng - ok > 1) {
int32_t mid = ok + (ng - ok) / 2;
(eval(mid) ? ok : ng) = mid;
}
return ok;
};
auto sub = [&](ssize_t offset, int32_t d) -> void {
int32_t ncarry = 0;
for(ssize_t i = 0; i < m; ++i) ncarry = store(lhs[i + offset], lhs[i + offset] - (int64_t)rhs[i] * d + ncarry);
if(m + offset < n) lhs.pop_back();
n = shrink(lhs);
};
for(ssize_t i = n - m; i >= 0; --i) {
res[i] = bisearch(i);
if(res[i] > 0) sub(i, res[i]);
}
if(res.back() == 0) res.pop_back();
return res;
}
void normalize(std::string_view sv, size_t n) {
assert(n > 0);
if(sv[0] == '+') {
normalize_unsigned(sv.substr(1), n - 1);
m_neg = false;
} else if(sv[0] == '-') {
normalize_unsigned(sv.substr(1), n - 1);
m_neg = !m_words.empty();
} else {
normalize_unsigned(sv, n);
m_neg = false;
}
}
void normalize_unsigned(std::string_view sv, size_t n) {
static constexpr uint32_t digits[BASE_DIGIT] = {1, 10, 100, 1'000, 10'000, 100'000, 1'000'000, 10'000'000, 100'000'000};
size_t m = (n + BASE_DIGIT - 1) / BASE_DIGIT;
m_words.assign(m, 0);
auto iter = sv.crbegin();
for(size_t i = 0; i < m; ++i) {
for(size_t j = 0; j < BASE_DIGIT and iter < sv.crend(); ++j, ++iter) m_words[i] += digits[j] * (*iter - '0');
}
shrink(m_words);
}
public:
Bigint() : m_words(), m_neg(false) {};
Bigint(int64_t n) : m_words(), m_neg(n < 0) {
n = std::abs(n);
while(n > 0) {
int32_t word;
n = store(word, n);
m_words.push_back(word);
}
}
Bigint(const char *c) : Bigint(std::string_view(c)) {}
Bigint(std::string_view s) {
std::stringstream ss;
ss << s;
ss >> *this;
}
explicit operator bool() const { return !is_zero(); }
Bigint operator+() const { return Bigint(*this); }
Bigint operator-() const {
Bigint res = *this;
return res.negate();
}
Bigint &operator++() { return *this += Bigint({1}, false); }
Bigint &operator--() { return *this -= Bigint({1}, false); }
Bigint operator++(int) {
Bigint res = *this;
++(*this);
return res;
}
Bigint operator--(int) {
Bigint res = *this;
--(*this);
return res;
}
Bigint &operator+=(const Bigint &rhs) {
if(is_negative() ^ rhs.is_negative()) {
m_neg ^= subtraction(m_words, m_words.size(), rhs.m_words, rhs.m_words.size());
if(m_words.empty()) m_neg = false;
} else {
addition(m_words, m_words.size(), rhs.m_words, rhs.m_words.size());
}
return *this;
}
Bigint &operator-=(const Bigint &rhs) {
if(is_negative() ^ rhs.is_negative()) {
addition(m_words, m_words.size(), rhs.m_words, rhs.m_words.size());
} else {
m_neg ^= subtraction(m_words, m_words.size(), rhs.m_words, rhs.m_words.size());
if(m_words.empty()) m_neg = false;
}
return *this;
}
Bigint &operator*=(const Bigint &rhs) { return *this = (*this) * rhs; }
Bigint &operator/=(const Bigint &rhs) {
assert(!rhs.is_zero());
m_words = division(m_words, m_words.size(), rhs.m_words, rhs.m_words.size());
m_neg = (m_words.empty() ? false : is_negative() ^ rhs.is_negative());
return *this;
}
Bigint &operator%=(const Bigint &rhs) {
assert(!rhs.is_zero());
division(m_words, m_words.size(), rhs.m_words, rhs.m_words.size());
if(m_words.empty()) m_neg = false;
return *this;
}
friend bool operator==(const Bigint &lhs, const Bigint &rhs) { return lhs.m_words == rhs.m_words and lhs.m_neg == rhs.m_neg; }
friend int operator<=>(const Bigint &lhs, const Bigint &rhs) { return compare(lhs, rhs); }
friend Bigint operator+(const Bigint &lhs, const Bigint &rhs) { return Bigint(lhs) += rhs; }
friend Bigint operator-(const Bigint &lhs, const Bigint &rhs) { return Bigint(lhs) -= rhs; }
friend Bigint operator*(const Bigint &lhs, const Bigint &rhs) {
if(lhs.is_zero() or rhs.is_zero()) return Bigint();
return Bigint(multiplication(lhs.m_words, lhs.m_words.size(), rhs.m_words, rhs.m_words.size()), lhs.is_negative() ^ rhs.is_negative());
}
friend Bigint operator/(const Bigint &lhs, const Bigint &rhs) { return Bigint(lhs) /= rhs; }
friend Bigint operator%(const Bigint &lhs, const Bigint &rhs) { return Bigint(lhs) %= rhs; }
friend std::istream &operator>>(std::istream &is, Bigint &rhs) {
std::string s;
is >> s;
assert(validate(s, s.size()));
rhs.normalize(s, s.size());
return is;
}
friend std::ostream &operator<<(std::ostream &os, const Bigint &rhs) {
if(rhs.is_zero()) return os << 0;
auto iter = rhs.m_words.crbegin();
os << (rhs.is_negative() ? "-" : "") << *iter++;
for(; iter < rhs.m_words.crend(); ++iter) os << std::setw(BASE_DIGIT) << std::setfill('0') << *iter;
return os;
}
static constexpr int32_t base() { return BASE; }
static constexpr size_t base_digit() { return BASE_DIGIT; }
const std::vector<int32_t> &words() const { return m_words; }
bool is_zero() const { return m_words.empty(); }
bool is_negative() const { return m_neg; }
int sign() const {
if(m_neg) return -1;
return (m_words.empty() ? 0 : 1);
}
Bigint abs() const { return Bigint(m_words, false); }
std::pair<Bigint, Bigint> divide(const Bigint &divisor) const {
assert(!divisor.is_zero());
auto remain = m_words;
auto &"ient = division(remain, remain.size(), divisor.m_words, divisor.m_words.size());
Bigint q(std::move(quotient), false), r(std::move(remain), false);
if(!q.is_zero()) q.m_neg = is_negative() ^ divisor.is_negative();
if(!r.is_zero()) r.m_neg = is_negative();
return {q, r};
}
Bigint &zeroize() {
zeroisation(m_words), m_neg = false;
return *this;
}
Bigint &negate() {
if(!m_words.empty()) m_neg = !m_neg;
return *this;
}
std::string to_string() const {
std::ostringstream oss;
oss << *this;
return oss.str();
}
};
} // namespace algorithm
#line 1 "algorithm/Math/NumberTheory/binary_bigint.hpp"
#line 7 "algorithm/Math/NumberTheory/binary_bigint.hpp"
#include <deque>
#line 9 "algorithm/Math/NumberTheory/binary_bigint.hpp"
#include <iostream>
#line 14 "algorithm/Math/NumberTheory/binary_bigint.hpp"
namespace algorithm {
class BinaryBigint {
static constexpr uint64_t BASE = 0x0000000100000000ULL;
static constexpr size_t BASE_DIGIT = 32;
static constexpr uint32_t SIGNBIT[2] = {0x00000000U, 0xffffffffU};
std::deque<uint32_t> m_words;
uint32_t m_signbit;
explicit BinaryBigint(const std::deque<uint32_t> &words, uint32_t signbit) : m_words(words), m_signbit(signbit) {}
explicit BinaryBigint(std::deque<uint32_t> &&words, uint32_t signbit) : m_words(std::move(words)), m_signbit(signbit) {}
static constexpr bool isdigit(char c) { return '0' <= c and c <= '9'; }
static constexpr bool isupper(char c) { return 'A' <= c and c <= 'F'; }
static constexpr bool islower(char c) { return 'a' <= c and c <= 'f'; }
static constexpr uint32_t ctoi(char c) {
if(isdigit(c)) return c - '0';
if(isupper(c)) return 10 + (c - 'A');
return 10 + (c - 'a');
}
static constexpr bool validate(std::string_view sv, size_t n) {
if(n == 0) return false;
if(sv[0] == '+' or sv[0] == '-') return validate_unsigned(sv.substr(1), n - 1);
return validate_unsigned(sv, n);
}
static constexpr bool validate_unsigned(std::string_view sv, size_t n) {
if(n == 0) return false;
return std::find_if_not(sv.cbegin(), sv.cend(), [](char c) -> bool { return isdigit(c) or isupper(c) or islower(c); }) == sv.cend();
}
static int compare(const BinaryBigint &lhs, const BinaryBigint &rhs) { return compare(lhs.m_words, lhs.m_words.size(), lhs.m_signbit, rhs.m_words, rhs.m_words.size(), rhs.m_signbit); }
static int compare(const std::deque<uint32_t> &lhs, ssize_t n, uint32_t lsb, const std::deque<uint32_t> &rhs, ssize_t m, uint32_t rsb) {
if(lsb ^ rsb) return (lsb ? -1 : 1);
if(n < m) return (lsb ? 1 : -1);
if(n > m) return (lsb ? -1 : 1);
for(ssize_t i = n - 1; i >= 0; --i) {
if(lhs[i] == rhs[i]) continue;
if(lhs[i] < rhs[i]) return -1;
return 1;
}
return 0;
}
static uint32_t store(uint32_t &word, uint64_t val) {
word = val;
return val >> BASE_DIGIT; // return carry.
}
static size_t shrink(std::deque<uint32_t> &words, uint32_t signbit) {
while(!words.empty() and words.back() == signbit) words.pop_back();
return words.size();
}
static size_t zeroisation(std::deque<uint32_t> &words, uint32_t &signbit) {
words.clear(), signbit = SIGNBIT[0];
return 0;
}
static size_t negation(std::deque<uint32_t> &words, uint32_t &signbit) {
words.push_back(signbit);
uint32_t ncarry = 1;
for(uint32_t &word : words) ncarry = store(word, (uint64_t)~word + ncarry);
signbit = ~signbit + ncarry;
return shrink(words, signbit);
}
static uint32_t bitwise_not(std::deque<uint32_t> &words, uint32_t &signbit) {
for(uint32_t &word : words) word = ~word;
signbit = ~signbit;
return words.size();
}
static void addition(std::deque<uint32_t> &lhs, size_t n, uint32_t &lsb, const std::deque<uint32_t> &rhs, size_t m, uint32_t rsb) {
n = std::max(n, m) + 1;
lhs.resize(n, lsb);
uint32_t carry = 0;
for(size_t i = 0; i < m; ++i) carry = store(lhs[i], (uint64_t)lhs[i] + rhs[i] + carry);
for(size_t i = m; i < n and rsb + carry; ++i) carry = store(lhs[i], (uint64_t)lhs[i] + rsb + carry);
lsb = lsb + rsb + carry;
shrink(lhs, lsb);
}
static void subtraction(std::deque<uint32_t> &lhs, size_t n, uint32_t &lsb, const std::deque<uint32_t> &rhs, size_t m, uint32_t rsb) {
n = std::max(n, m) + 1;
lhs.resize(n, lsb);
uint32_t ncarry = 1;
for(size_t i = 0; i < m; ++i) ncarry = store(lhs[i], (uint64_t)lhs[i] + ~rhs[i] + ncarry);
for(size_t i = m; i < n and ~rsb + ncarry; ++i) ncarry = store(lhs[i], (uint64_t)lhs[i] + ~rsb + ncarry);
lsb = lsb + ~rsb + ncarry;
shrink(lhs, lsb);
}
static std::pair<std::deque<uint32_t>, uint32_t> multiplication(const std::deque<uint32_t> &lhs, size_t n, uint32_t lsb, const std::deque<uint32_t> &rhs, size_t m, uint32_t rsb) {
std::deque<uint32_t> words(n + m, 0);
uint32_t signbit = lsb ^ rsb;
for(size_t j = 0; j < m; ++j) {
if(!rhs[j]) continue;
uint32_t carry = 0;
for(size_t i = 0; i < n; ++i) carry = store(words[i + j], words[i + j] + (uint64_t)lhs[i] * rhs[j] + carry);
words[j + n] = carry;
}
if(rsb) {
uint32_t ncarry = 1;
for(size_t i = 0; i < n; ++i) ncarry = store(words[i + m], (uint64_t)words[i + m] + ~lhs[i] + ncarry);
}
if(lsb) {
uint32_t ncarry = 1;
for(size_t j = 0; j < m; ++j) ncarry = store(words[j + n], (uint64_t)words[j + n] + ~rhs[j] + ncarry);
}
shrink(words, signbit);
return {words, signbit};
}
static std::pair<std::deque<uint32_t>, uint32_t> division(std::deque<uint32_t> &lhs, ssize_t n, uint32_t &lsb, const std::deque<uint32_t> &rhs, ssize_t m, uint32_t rsb) {
if(m == 0) {
assert(rsb != SIGNBIT[0]);
auto words = lhs;
uint32_t signbit = lsb;
negation(words, signbit), zeroisation(lhs, lsb);
return {words, signbit};
}
if(lsb ^ rsb) {
n = negation(lhs, lsb);
auto &&[words, signbit] = division(lhs, n, lsb, rhs, m, rsb);
negation(words, signbit), negation(lhs, lsb);
return {words, signbit};
}
std::deque<uint32_t> words;
uint32_t signbit = SIGNBIT[0];
lhs.push_back(lsb), ++n;
auto bisearch = [&](ssize_t offset) -> uint32_t {
auto eval = [&](uint32_t d) -> bool {
uint32_t tmp;
uint32_t carry = 0, ncarry = 1;
for(ssize_t i = 0; i < m; ++i) {
carry = store(tmp, (uint64_t)rhs[i] * d + carry);
ncarry = store(tmp, (uint64_t)lhs[i + offset] + ~tmp + ncarry);
}
carry = store(tmp, (uint64_t)rsb * d + carry);
ncarry = store(tmp, (uint64_t)lhs[m + offset] + ~tmp + ncarry);
uint32_t last = lsb + ~(rsb * d + carry) + ncarry;
return last == lsb;
};
uint64_t ok = 0, ng = BASE;
while(ng - ok > 1) {
uint64_t mid = ok + (ng - ok) / 2;
(eval(mid) ? ok : ng) = mid;
}
return ok;
};
auto sub = [&](ssize_t offset, uint32_t d) -> void {
uint32_t carry = 0, ncarry = 1;
for(ssize_t i = 0; i < m; ++i) {
uint32_t tmp;
carry = store(tmp, (uint64_t)rhs[i] * d + carry);
ncarry = store(lhs[i + offset], (uint64_t)lhs[i + offset] + ~tmp + ncarry);
}
lhs.pop_back();
};
for(ssize_t i = n - m - 1; i >= 0; --i) {
uint32_t d = bisearch(i);
words.push_front(d);
sub(i, d);
}
shrink(words, signbit), n = shrink(lhs, lsb);
if(lsb and compare(lhs, n, lsb, rhs, m, rsb) == 0) addition(words, words.size(), signbit, {1}, 1, SIGNBIT[0]), zeroisation(lhs, lsb);
return {words, signbit};
}
static void shift_left(std::deque<uint32_t> &words, size_t n, uint32_t signbit, size_t k) {
size_t t = k / BASE_DIGIT;
k -= 32ULL * t;
uint32_t carry = 0;
for(size_t i = 0; i < n; ++i) {
uint32_t word = words[i];
words[i] = word << k | carry;
carry = word >> (BASE_DIGIT - k);
}
words.push_back(signbit << k | carry);
for(size_t i = 0; i < t; ++i) words.push_front(SIGNBIT[0]);
shrink(words, signbit);
}
static void shift_right(std::deque<uint32_t> &words, size_t n, uint32_t signbit, size_t k) {
if(k >= 32ULL * n) {
words.clear();
return;
}
size_t t = k / BASE_DIGIT;
for(size_t i = 0; i < t; ++i) words.pop_front();
n -= t, k -= 32ULL * t;
for(size_t i = 0; i < n - 1; ++i) words[i] = words[i + 1] << (BASE_DIGIT - k) | words[i] >> k;
words[n - 1] = signbit << (BASE_DIGIT - k) | words[n - 1] >> k;
shrink(words, signbit);
}
static void bitwise_and(std::deque<uint32_t> &lhs, size_t n, uint32_t &lsb, const std::deque<uint32_t> &rhs, size_t m, uint32_t rsb) {
n = std::max(n, m);
lhs.resize(n, lsb);
for(size_t i = 0; i < m; ++i) lhs[i] &= rhs[i];
for(size_t i = m; i < n; ++i) lhs[i] &= rsb;
lsb &= rsb;
shrink(lhs, lsb);
}
static void bitwise_or(std::deque<uint32_t> &lhs, size_t n, uint32_t &lsb, const std::deque<uint32_t> &rhs, size_t m, uint32_t rsb) {
n = std::max(n, m);
lhs.resize(n, lsb);
for(size_t i = 0; i < m; ++i) lhs[i] |= rhs[i];
for(size_t i = m; i < n; ++i) lhs[i] |= rsb;
lsb |= rsb;
shrink(lhs, lsb);
}
static void bitwise_xor(std::deque<uint32_t> &lhs, size_t n, uint32_t &lsb, const std::deque<uint32_t> &rhs, size_t m, uint32_t rsb) {
n = std::max(n, m);
lhs.resize(n, lsb);
for(size_t i = 0; i < m; ++i) lhs[i] ^= rhs[i];
for(size_t i = m; i < n; ++i) lhs[i] ^= rsb;
lsb ^= rsb;
shrink(lhs, lsb);
}
static bool bitwise_test(const std::deque<uint32_t> &words, size_t n, uint32_t signbit, size_t pos) {
size_t t = pos / BASE_DIGIT;
pos -= BASE_DIGIT * t;
if(t < n) return words[t] >> pos & 1U;
return signbit;
}
static void bitwise_set(std::deque<uint32_t> &words, size_t n, uint32_t signbit, size_t pos) {
size_t t = pos / BASE_DIGIT;
pos -= BASE_DIGIT * t;
if(t < n) {
words[t] |= 1U << pos;
shrink(words, signbit);
return;
}
if(signbit) return;
words.resize(t + 1, SIGNBIT[0]);
words[t] |= 1U << pos;
}
static void bitwise_reset(std::deque<uint32_t> &words, size_t n, uint32_t signbit, size_t pos) {
size_t t = pos / BASE_DIGIT;
pos -= BASE_DIGIT * t;
if(t < n) {
words[t] &= ~(1U << pos);
shrink(words, signbit);
return;
}
if(!signbit) return;
words.resize(t + 1, SIGNBIT[1]);
words[t] &= ~(1U << pos);
}
void normalize(std::string_view sv, size_t n) {
assert(n > 0);
if(sv[0] == '+') {
normalize_unsigned(sv.substr(1), n - 1);
} else if(sv[0] == '-') {
normalize_unsigned(sv.substr(1), n - 1);
negation(m_words, m_signbit);
} else {
normalize_unsigned(sv, n);
}
}
void normalize_unsigned(std::string_view sv, size_t n) {
size_t m = (n + 7) / 8;
m_words.assign(m, SIGNBIT[0]);
auto iter = sv.crbegin();
for(size_t i = 0; i < m; ++i) {
for(size_t j = 0; j < BASE_DIGIT and iter < sv.crend(); j += 4, ++iter) m_words[i] |= ctoi(*iter) << j;
}
shrink(m_words, SIGNBIT[0]);
m_signbit = SIGNBIT[0];
}
public:
BinaryBigint() : m_words(), m_signbit(SIGNBIT[0]) {}
BinaryBigint(int64_t n) : m_words({(uint32_t)n, uint32_t(n >> BASE_DIGIT)}), m_signbit(SIGNBIT[n < 0]) {
shrink(m_words, m_signbit);
}
BinaryBigint(const char *c) : BinaryBigint(std::string_view(c)) {}
BinaryBigint(std::string_view sv) {
std::stringstream ss;
ss << sv;
ss >> *this;
}
explicit operator bool() const { return !is_zero(); }
BinaryBigint operator+() const { return BinaryBigint(*this); }
BinaryBigint operator-() const {
BinaryBigint res = *this;
return res.negate();
}
BinaryBigint operator~() const {
BinaryBigint res = *this;
return res.bitwise_not();
}
BinaryBigint &operator++() {
addition(m_words, m_words.size(), m_signbit, {1}, 1, SIGNBIT[0]);
return *this;
}
BinaryBigint &operator--() {
addition(m_words, m_words.size(), m_signbit, {}, 0, SIGNBIT[1]);
return *this;
}
BinaryBigint operator++(int) {
BinaryBigint res = *this;
++(*this);
return res;
}
BinaryBigint operator--(int) {
BinaryBigint res = *this;
--(*this);
return res;
}
BinaryBigint &operator+=(const BinaryBigint &rhs) {
addition(m_words, m_words.size(), m_signbit, rhs.m_words, rhs.m_words.size(), rhs.m_signbit);
return *this;
}
BinaryBigint &operator-=(const BinaryBigint &rhs) {
subtraction(m_words, m_words.size(), m_signbit, rhs.m_words, rhs.m_words.size(), rhs.m_signbit);
return *this;
}
BinaryBigint &operator*=(const BinaryBigint &rhs) { return *this = (*this) * rhs; }
BinaryBigint &operator/=(const BinaryBigint &rhs) {
assert(!rhs.is_zero());
auto &&[words, signbit] = division(m_words, m_words.size(), m_signbit, rhs.m_words, rhs.m_words.size(), rhs.m_signbit);
m_words = std::move(words), m_signbit = signbit;
return *this;
}
BinaryBigint &operator%=(const BinaryBigint &rhs) {
assert(!rhs.is_zero());
division(m_words, m_words.size(), m_signbit, rhs.m_words, rhs.m_words.size(), rhs.m_signbit);
return *this;
}
BinaryBigint &operator<<=(size_t k) {
shift_left(m_words, m_words.size(), m_signbit, k);
return *this;
}
BinaryBigint &operator>>=(size_t k) {
shift_right(m_words, m_words.size(), m_signbit, k);
return *this;
}
BinaryBigint &operator&=(const BinaryBigint &rhs) {
bitwise_and(m_words, m_words.size(), m_signbit, rhs.m_words, rhs.m_words.size(), rhs.m_signbit);
return *this;
}
BinaryBigint &operator|=(const BinaryBigint &rhs) {
bitwise_or(m_words, m_words.size(), m_signbit, rhs.m_words, rhs.m_words.size(), rhs.m_signbit);
return *this;
}
BinaryBigint &operator^=(const BinaryBigint &rhs) {
bitwise_xor(m_words, m_words.size(), m_signbit, rhs.m_words, rhs.m_words.size(), rhs.m_signbit);
return *this;
}
friend bool operator==(const BinaryBigint &lhs, const BinaryBigint &rhs) { return lhs.m_words == rhs.m_words and lhs.m_signbit == rhs.m_signbit; }
friend int operator<=>(const BinaryBigint &lhs, const BinaryBigint &rhs) { return compare(lhs, rhs); }
friend BinaryBigint operator+(const BinaryBigint &lhs, const BinaryBigint &rhs) { return BinaryBigint(lhs) += rhs; }
friend BinaryBigint operator-(const BinaryBigint &lhs, const BinaryBigint &rhs) { return BinaryBigint(lhs) -= rhs; }
friend BinaryBigint operator*(const BinaryBigint &lhs, const BinaryBigint &rhs) {
if(lhs.is_zero() or rhs.is_zero()) return BinaryBigint();
auto &&[words, signbit] = multiplication(lhs.m_words, lhs.m_words.size(), lhs.m_signbit, rhs.m_words, rhs.m_words.size(), rhs.m_signbit);
return BinaryBigint(std::move(words), signbit);
}
friend BinaryBigint operator/(const BinaryBigint &lhs, const BinaryBigint &rhs) { return BinaryBigint(lhs) /= rhs; }
friend BinaryBigint operator%(const BinaryBigint &lhs, const BinaryBigint &rhs) { return BinaryBigint(lhs) %= rhs; }
friend BinaryBigint operator<<(const BinaryBigint &lhs, size_t k) { return BinaryBigint(lhs) <<= k; }
friend BinaryBigint operator>>(const BinaryBigint &lhs, size_t k) { return BinaryBigint(lhs) >>= k; }
friend BinaryBigint operator&(const BinaryBigint &lhs, const BinaryBigint &rhs) { return BinaryBigint(lhs) &= rhs; }
friend BinaryBigint operator|(const BinaryBigint &lhs, const BinaryBigint &rhs) { return BinaryBigint(lhs) |= rhs; }
friend BinaryBigint operator^(const BinaryBigint &lhs, const BinaryBigint &rhs) { return BinaryBigint(lhs) ^= rhs; }
friend std::istream &operator>>(std::istream &is, BinaryBigint &rhs) {
std::string s;
is >> s;
assert(validate(s, s.size()));
rhs.normalize(s, s.size());
return is;
}
friend std::ostream &operator<<(std::ostream &os, const BinaryBigint &rhs) {
if(rhs.is_negative()) return os << "-" << -rhs;
if(rhs.is_zero()) return os << 0;
auto old = os.setf(std::ios_base::hex, std::ios_base::basefield); // 16進数表示．
auto iter = rhs.m_words.crbegin();
os << *iter++;
for(; iter < rhs.m_words.crend(); ++iter) os << std::setw(8) << std::setfill('0') << *iter;
os.flags(old);
return os;
}
static constexpr uint64_t base() { return BASE; }
static constexpr size_t base_digit() { return BASE_DIGIT; }
const std::deque<uint32_t> &words() const { return m_words; }
uint32_t signbit() const { return m_signbit; }
bool is_zero() const { return m_words.empty() and !m_signbit; }
bool is_negative() const { return m_signbit; }
int sign() const {
if(m_signbit) return -1;
return (m_words.empty() ? 0 : 1);
}
BinaryBigint abs() const { return (is_negative() ? -(*this) : BinaryBigint(*this)); }
std::pair<BinaryBigint, BinaryBigint> divide(const BinaryBigint &divisor) const {
assert(!divisor.is_zero());
auto remain = *this;
auto &&[words, signbit] = division(remain.m_words, remain.m_words.size(), remain.m_signbit, divisor.m_words, divisor.m_words.size(), divisor.m_signbit);
return {BinaryBigint(std::move(words), signbit), std::move(remain)};
}
BinaryBigint &zeroise() {
zeroisation(m_words, m_signbit);
return *this;
}
BinaryBigint &negate() {
negation(m_words, m_signbit);
return *this;
}
BinaryBigint &bitwise_not() {
bitwise_not(m_words, m_signbit);
return *this;
}
bool test(size_t k) const { return bitwise_test(m_words, m_words.size(), m_signbit, k); }
BinaryBigint &set(size_t k, bool val = true) {
if(!val) return reset(k);
bitwise_set(m_words, m_words.size(), m_signbit, k);
return *this;
}
BinaryBigint &reset(size_t k) {
bitwise_reset(m_words, m_words.size(), m_signbit, k);
return *this;
}
std::string to_string() const {
std::ostringstream oss;
oss << *this;
return oss.str();
}
};
} // namespace algorithm
#line 6 "algorithm/Math/NumberTheory/bigint_utils.hpp"
namespace algorithm {
BinaryBigint dtoh(const Bigint &a) {
BinaryBigint res;
for(auto iter = a.words().crbegin(); iter < a.words().crend(); ++iter) {
res *= Bigint::base();
res += *iter;
}
if(a.is_negative()) res.negate();
return res;
};
Bigint htod(const BinaryBigint &a) {
if(a.is_negative()) return htod(-a).negate();
Bigint res;
for(auto iter = a.words().crbegin(); iter < a.words().crend(); ++iter) {
res *= BinaryBigint::base();
res += *iter;
}
return res;
};
} // namespace algorithm