#1116079 (C++23) No.3250 最小公倍数

提出ソース

結果

問題	No.3250 最小公倍数
ユーザー	mihhiael
提出日時	2025-08-29 23:06:39
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,572 ms / 2,000 ms
コード長	55,573 bytes
コンパイル時間	2,951 ms
コンパイル使用メモリ	200,576 KB
実行使用メモリ	56,712 KB
最終ジャッジ日時	2025-08-29 23:07:02
合計ジャッジ時間	17,475 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
sample	AC * 1
other	AC * 21

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

ソースコード

raw source code

#pragma once




























#if defined _CPPUNWIND || defined __cpp_exceptions
#define QC_HASH_EXCEPTIONS_ENABLED
#endif
#include <bit>
#include <cstdint>
#include <cstring>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#ifdef QC_HASH_EXCEPTIONS_ENABLED
#include <stdexcept>
#endif
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>
namespace qc::hash {



using u64 = uint64_t;
using s64 = int64_t;
using f64 = double;
using u32 = uint32_t;
using s32 = int32_t;
using f32 = float;
using u16 = uint16_t;
using s16 = int16_t;
using u8 = uint8_t;
using s8 = int8_t;

static_assert(std::is_same_v<u64, u64> && std::is_same_v<uintptr_t, u64>,
 "Unsupported architecture");
inline namespace config {








inline constexpr u64 minMapCapacity{16u};
}


template<typename T>
concept SignedInteger = std::is_same_v<T, s64> || std::is_same_v<T, s32>
 || std::is_same_v<T, s16> || std::is_same_v<T, s8>;
template<typename T>
concept UnsignedInteger = std::is_same_v<T, u64> || std::is_same_v<T, u32>
 || std::is_same_v<T, u16> || std::is_same_v<T, u8>;
template<typename T>
concept Enum = std::is_enum_v<T>;
template<typename T>
concept Pointer = std::is_pointer_v<T>;
namespace _private {
template<u64 size>
struct UnsignedHelper;
template<>
struct UnsignedHelper<1u> {
	using type = u8;
};
template<>
struct UnsignedHelper<2u> {
	using type = u16;
};
template<>
struct UnsignedHelper<4u> {
	using type = u32;
};
template<>
struct UnsignedHelper<8u> {
	using type = u64;
};
}


template<u64 size>
using Unsigned = typename _private::UnsignedHelper<size>::type;











template<u64 elementSize, u64 elementN>
struct UnsignedMulti {
	using Element = Unsigned<elementSize>;
	Element elements[elementN];
	constexpr bool operator==(const UnsignedMulti &) const = default;
	constexpr UnsignedMulti operator~() const;
};





template<typename T>
struct IsUniquelyRepresentable
	: std::bool_constant<std::has_unique_object_representations_v<T>> {};
template<typename T>
struct IsUniquelyRepresentable<std::unique_ptr<T>> : std::true_type {};
template<typename T>
struct IsUniquelyRepresentable<std::shared_ptr<T>> : std::true_type {};
template<typename T1, typename T2>
struct IsUniquelyRepresentable<std::pair<T1, T2>>
	: std::bool_constant<IsUniquelyRepresentable<T1>::value
 && IsUniquelyRepresentable<T2>::value> {};
template<typename CharT, typename Traits>
struct IsUniquelyRepresentable<std::basic_string_view<CharT, Traits>>
	: std::false_type {};





template<typename T>
concept Rawable = IsUniquelyRepresentable<T>::value;
namespace _private {
template<typename T>
struct RawTypeHelper {
	using type = Unsigned<sizeof(T)>;
};
template<typename T>
requires (alignof(T) != sizeof(T) || sizeof(T) > sizeof(uintmax_t))
struct RawTypeHelper<T> {
	static constexpr u64 align{
 alignof(T) > alignof(uintmax_t) ? alignof(uintmax_t) : alignof(T)};
	using type = UnsignedMulti<align, sizeof(T) / align>;
};
}



template<typename T>
using RawType = typename _private::RawTypeHelper<T>::type;











template<Rawable T>
struct IdentityHash;





template<typename T>
struct IdentityHash<T *>;




template<typename T>
struct IdentityHash<std::unique_ptr<T>>;




template<typename T>
struct IdentityHash<std::shared_ptr<T>>;













template<typename T>
struct FastHash;




template<typename T>
struct FastHash<T *>;



template<typename T>
struct FastHash<std::unique_ptr<T>>;



template<typename T>
struct FastHash<std::shared_ptr<T>>;



template<>
struct FastHash<std::string>;



template<>
struct FastHash<std::string_view>;
namespace fastHash {






template<UnsignedInteger H>
[[nodiscard]] constexpr H mix(H v);






template<UnsignedInteger H, typename T>
[[nodiscard]] constexpr H hash(const T &v);







template<UnsignedInteger H>
[[nodiscard]] H hash(const void *data, u64 length);
}



template<typename K, typename KOther>
struct IsCompatible
	: std::bool_constant<std::is_same_v<std::decay_t<K>, std::decay_t<KOther>>> {
};
template<SignedInteger K, SignedInteger KOther>
struct IsCompatible<K, KOther>
	: std::bool_constant<sizeof(KOther) <= sizeof(K)> {};
template<UnsignedInteger K, UnsignedInteger KOther>
struct IsCompatible<K, KOther>
	: std::bool_constant<sizeof(KOther) <= sizeof(K)> {};
template<SignedInteger K, UnsignedInteger KOther>
struct IsCompatible<K, KOther>
	: std::bool_constant<sizeof(KOther) < sizeof(K)> {};
template<UnsignedInteger K, SignedInteger KOther>
struct IsCompatible<K, KOther> : std::false_type {};
template<typename T, typename TOther>
requires (std::is_same_v<std::decay_t<T>, std::decay_t<TOther>>
 || std::is_base_of_v<T, TOther>)
struct IsCompatible<T *, TOther *> : std::true_type {};
template<typename T, typename TOther>
requires (std::is_same_v<std::decay_t<T>, std::decay_t<TOther>>
 || std::is_base_of_v<T, TOther>)
struct IsCompatible<std::unique_ptr<T>, TOther *> : std::true_type {};
template<typename T, typename TOther>
requires (std::is_same_v<std::decay_t<T>, std::decay_t<TOther>>
 || std::is_base_of_v<T, TOther>)
struct IsCompatible<std::shared_ptr<T>, TOther *> : std::true_type {};




template<typename KOther, typename K>
concept Compatible =
	Rawable<K> && Rawable<KOther> && IsCompatible<K, KOther>::value;

struct RawFriend;
















template<Rawable K, typename V, typename H = IdentityHash<K>,
 typename A = std::allocator<std::pair<K, V>>>
class RawMap;


















template<Rawable K, typename H = IdentityHash<K>,
 typename A = std::allocator<K>>
using RawSet = RawMap<K, void, H, A>;
template<Rawable K, typename V, typename H, typename A>
class RawMap {
	inline static constexpr bool _isSet{std::is_same_v<V, void>};
	inline static constexpr bool _isMap{! _isSet};
   	using E = std::conditional_t<_isSet, K, std::pair<K, V>>;
  	template<bool constant>
	class _Iterator;
	friend ::qc::hash::RawFriend;
	public:
	static_assert(std::is_move_constructible_v<E>);
	static_assert(std::is_move_assignable_v<E>);
	static_assert(std::is_swappable_v<E>);
	static_assert(requires(const H h, const K k) { u64{h(k)}; });
	static_assert(std::is_move_constructible_v<H>);
	static_assert(std::is_move_assignable_v<H>);
	static_assert(std::is_swappable_v<H>);
	static_assert(std::is_move_constructible_v<A>);
	static_assert(std::is_move_assignable_v<A>
 || ! std::allocator_traits<
 A>::propagate_on_container_move_assignment::value);
	static_assert(
 std::is_swappable_v<A>
 || ! std::allocator_traits<A>::propagate_on_container_swap::value);
	using key_type = K;
	using mapped_type = V;
	using value_type = E;
	using hasher = H;
	using allocator_type = A;
	using reference = E &;
	using const_reference = const E &;
	using pointer = E *;
	using const_pointer = const E *;
	using size_type = u64;
	using difference_type = s64;
	using iterator = _Iterator<false>;
	using const_iterator = _Iterator<true>;
            	explicit RawMap(u64 capacity = minMapCapacity, const H &hash = {},
 const A &alloc = {});
	RawMap(u64 capacity, const A &alloc);
	explicit RawMap(const A &alloc);
              	template<typename It>
	RawMap(It first, It last, u64 capacity = {}, const H &hash = {},
 const A &alloc = {});
	template<typename It>
	RawMap(It first, It last, u64 capacity, const A &alloc);
             	RawMap(std::initializer_list<E> elements, u64 capacity = {},
 const H &hash = {}, const A &alloc = {});
	RawMap(std::initializer_list<E> elements, u64 capacity, const A &alloc);
     	RawMap(const RawMap &other);
        	RawMap(RawMap &&other);
       	RawMap &operator=(std::initializer_list<E> elements);
       	RawMap &operator=(const RawMap &other);
      	RawMap &operator=(RawMap &&other);
   	~RawMap();
         	std::pair<iterator, bool> insert(const E &element);
         	std::pair<iterator, bool> insert(E &&element);
         	template<typename It>
	void insert(It first, It last);
        	void insert(std::initializer_list<E> elements);
         	std::pair<iterator, bool> emplace(const E &element);
         	std::pair<iterator, bool> emplace(E &&element);
             	template<typename K_, typename V_>
	std::pair<iterator, bool> emplace(K_ &&key, V_ &&value)
	requires (! std::is_same_v<V, void>);
            	template<typename... KArgs>
	std::pair<iterator, bool> emplace(KArgs &&...keyArgs)
	requires (std::is_same_v<V, void>);
              	template<typename... KArgs, typename... VArgs>
	std::pair<iterator, bool> emplace(std::piecewise_construct_t,
 std::tuple<KArgs...> &&keyArgs,
 std::tuple<VArgs...> &&valueArgs)
	requires (! std::is_same_v<V, void>);
             	template<typename K_, typename... VArgs>
	std::pair<iterator, bool> try_emplace(K_ &&key, VArgs &&...valueArgs);
        	template<Compatible<K> K_>
	bool erase(const K_ &key);
         	void erase(iterator position);
       	void clear();
    	template<Compatible<K> K_>
	[[nodiscard]] bool contains(const K_ &key) const;
    	template<Compatible<K> K_>
	[[nodiscard]] u64 count(const K_ &key) const;
#ifdef QC_HASH_EXCEPTIONS_ENABLED
         	template<Compatible<K> K_>
	[[nodiscard]] std::add_lvalue_reference_t<V> at(const K_ &key)
	requires (! std::is_same_v<V, void>);
	template<Compatible<K> K_>
	[[nodiscard]] std::add_lvalue_reference_t<const V> at(const K_ &key) const
	requires (! std::is_same_v<V, void>);
#endif
         	template<Compatible<K> K_>
	[[nodiscard]] std::add_lvalue_reference_t<V> operator[](const K_ &key)
	requires (! std::is_same_v<V, void>);
	template<Compatible<K> K_>
	[[nodiscard]] std::add_lvalue_reference_t<V> operator[](K_ &&key)
	requires (! std::is_same_v<V, void>);
   	[[nodiscard]] iterator begin();
	[[nodiscard]] const_iterator begin() const;
	[[nodiscard]] const_iterator cbegin() const;
    	[[nodiscard]] iterator end();
	[[nodiscard]] const_iterator end() const;
	[[nodiscard]] const_iterator cend() const;
     	template<Compatible<K> K_>
	[[nodiscard]] iterator find(const K_ &key);
	template<Compatible<K> K_>
	[[nodiscard]] const_iterator find(const K_ &key) const;
   	template<Compatible<K> K_>
	[[nodiscard]] u64 slot(const K_ &key) const;
          	void reserve(u64 capacity);
           	void rehash(u64 slotN);
         	void swap(RawMap &other);
   	[[nodiscard]] u64 size() const;
   	[[nodiscard]] bool empty() const;
    	[[nodiscard]] u64 capacity() const;
    	[[nodiscard]] u64 slot_n() const;
    	[[nodiscard]] u64 max_size() const;
   	[[nodiscard]] u64 max_slot_n() const;
   	[[nodiscard]] f32 load_factor() const;
   	[[nodiscard]] f32 max_load_factor() const;
   	[[nodiscard]] const H &hash_function() const;
   	[[nodiscard]] const A &get_allocator() const;
	private:
	using _RawKey = RawType<K>;
	inline static constexpr _RawKey _vacantKey{_RawKey(~_RawKey{})};
	inline static constexpr _RawKey _graveKey{_RawKey(~_RawKey{1u})};
	inline static constexpr _RawKey _specialKeys[2]{_graveKey, _vacantKey};
	inline static constexpr _RawKey _vacantGraveKey{_vacantKey};
	inline static constexpr _RawKey _vacantVacantKey{_graveKey};
	inline static constexpr _RawKey _vacantSpecialKeys[2]{_vacantGraveKey,
 _vacantVacantKey};
	inline static constexpr _RawKey _terminalKey{0u};
	static K &_key(E &element);
	static const K &_key(const E &element);
	static bool _isPresent(const _RawKey &key);
	static bool _isSpecial(const _RawKey &key);
	u64 _size;
	u64 _slotN; 	E *_elements;
	bool _haveSpecial[2];
	H _hash;
	A _alloc;
	template<typename KTuple, typename VTuple, u64... kIndices, u64... vIndices>
	std::pair<iterator, bool> _emplace(KTuple &&kTuple, VTuple &&vTuple,
 std::index_sequence<kIndices...>,
 std::index_sequence<vIndices...>);
	template<bool preserveInvariants>
	void _clear();
	template<Compatible<K> K_>
	u64 _slot(const K_ &key) const;
	void _rehash(u64 slotN);
	template<bool zeroControls>
	void _allocate();
	void _deallocate();
	void _clearKeys();
	template<bool move>
	void _forwardData(std::conditional_t<move, RawMap, const RawMap> &other);
	struct _FindKeyResult1 {
 E *element;
 bool isPresent;
	};
	struct _FindKeyResult2 {
 E *element;
 bool isPresent;
 bool isSpecial;
 unsigned char specialI;
	};
	template<bool insertionForm>
	using _FindKeyResult =
 std::conditional_t<insertionForm, _FindKeyResult2, _FindKeyResult1>;
 	template<bool insertionForm, Compatible<K> K_>
	_FindKeyResult<insertionForm> _findKey(const K_ &key) const;
};
template<Rawable K, typename V, typename H, typename A>
bool operator==(const RawMap<K, V, H, A> &m1, const RawMap<K, V, H, A> &m2);
template<Rawable K, typename V, typename H, typename A>
template<bool constant>
class RawMap<K, V, H, A>::_Iterator {
	friend ::qc::hash::RawMap<K, V, H, A>;
	friend ::qc::hash::RawFriend;
	using E = std::conditional_t<constant, const RawMap::E, RawMap::E>;
	public:
	using iterator_category = std::forward_iterator_tag;
	using value_type = E;
	using difference_type = ptrdiff_t;
	using pointer = E *;
	using reference = E &;
   	constexpr _Iterator() = default;
     	constexpr _Iterator(const _Iterator &other) = default;
	template<bool constant_>
	requires (constant && ! constant_)
	constexpr _Iterator(const _Iterator<constant_> &other);
     	_Iterator &operator=(const _Iterator &other) = default;
	template<bool constant_>
	requires (constant && ! constant_)
	_Iterator &operator=(const _Iterator<constant_> &other);
    	[[nodiscard]] E &operator*() const;
    	[[nodiscard]] E *operator->() const;
        	_Iterator &operator++();
        	_Iterator operator++(int);
    	template<bool constant_>
	[[nodiscard]] bool operator==(const _Iterator<constant_> &other) const;
	private:
	E *_element;
	constexpr _Iterator(E *element);
};
} namespace std {






template<typename K, typename V, typename H, typename A>
void swap(qc::hash::RawMap<K, V, H, A> &a, qc::hash::RawMap<K, V, H, A> &b);
}
namespace qc::hash {
namespace _private {
inline constexpr u64 minMapSlotN{minMapCapacity * 2u};

template<UnsignedInteger U, typename T>
inline constexpr U getLowBytes(const T &v) {
 	if constexpr(alignof(T) >= sizeof(U)) {
 return reinterpret_cast<const U &>(v);
	}
  	else if constexpr(alignof(T) == sizeof(T)) {
 return reinterpret_cast<const Unsigned<sizeof(T)> &>(v);
	}
   	else {
 U result{0u};
 using Block = Unsigned<alignof(T) < sizeof(U) ? alignof(T) : sizeof(U)>;
 constexpr u64 n{(sizeof(T) < sizeof(U) ? sizeof(T) : sizeof(U))
 / sizeof(Block)};
 const Block *src{reinterpret_cast<const Block *>(&v)};
 Block *dst{reinterpret_cast<Block *>(&result)};
  if constexpr(std::endian::native == std::endian::big) {
 constexpr u64 srcBlocks{sizeof(T) / sizeof(Block)};
 constexpr u64 dstBlocks{sizeof(U) / sizeof(Block)};
 if constexpr(srcBlocks > n) {
 src += srcBlocks - n;
 }
 if constexpr(dstBlocks > n) {
 dst += dstBlocks - n;
 }
 }
  if constexpr(n >= 1u) dst[0] = src[0];
 if constexpr(n >= 2u) dst[1] = src[1];
 if constexpr(n >= 3u) dst[2] = src[2];
 if constexpr(n >= 4u) dst[3] = src[3];
 if constexpr(n >= 5u) dst[4] = src[4];
 if constexpr(n >= 6u) dst[5] = src[5];
 if constexpr(n >= 7u) dst[6] = src[6];
 if constexpr(n >= 8u) dst[7] = src[7];
 return result;
	}
}
} template<u64 elementSize, u64 elementN>
inline constexpr auto UnsignedMulti<elementSize, elementN>::operator~() const
	-> UnsignedMulti {
	UnsignedMulti res;
	for(u64 i{0u}; i < elementN; ++i) {
 res.elements[i] = Element(~elements[i]);
	}
	return res;
}
template<Rawable T>
struct IdentityHash {
	[[nodiscard]] constexpr u64 operator()(const T &v) const {
 return _private::getLowBytes<u64>(v);
	}
};
template<typename T>
struct IdentityHash<T *> {
	[[nodiscard]] constexpr u64 operator()(const T *const v) const {
  constexpr s32 shift{s32(std::bit_width(alignof(T)) - 1u)};
 return std::bit_cast<u64>(v) >> shift;
	}
};
template<typename T>
struct IdentityHash<std::unique_ptr<T>> : IdentityHash<T *> {
 	using IdentityHash<T *>::operator();
	[[nodiscard]] constexpr u64 operator()(const std::unique_ptr<T> &v) const {
 return (*this)(v.get());
	}
};
template<typename T>
struct IdentityHash<std::shared_ptr<T>> : IdentityHash<T *> {
 	using IdentityHash<T *>::operator();
	[[nodiscard]] constexpr u64 operator()(const std::shared_ptr<T> &v) const {
 return (*this)(v.get());
	}
};
template<typename T>
struct FastHash {
	[[nodiscard]] constexpr u64 operator()(const T &v) const {
 return fastHash::hash<u64>(v);
	}
};
template<typename T>
struct FastHash<T *> {
	[[nodiscard]] constexpr u64 operator()(const T *const v) const {
 return fastHash::hash<u64>(v);
	}
};
template<typename T>
struct FastHash<std::unique_ptr<T>> : FastHash<T *> {
 	using FastHash<T *>::operator();
	[[nodiscard]] constexpr u64 operator()(const std::unique_ptr<T> &v) const {
 return (*this)(v.get());
	}
};
template<typename T>
struct FastHash<std::shared_ptr<T>> : FastHash<T *> {
 	using FastHash<T *>::operator();
	[[nodiscard]] constexpr u64 operator()(const std::shared_ptr<T> &v) const {
 return (*this)(v.get());
	}
};
template<>
struct FastHash<std::string> {
	[[nodiscard]] u64 operator()(const std::string &v) const {
 return fastHash::hash<u64>(v.c_str(), v.length());
	}
	[[nodiscard]] u64 operator()(const std::string_view &v) const {
 return fastHash::hash<u64>(v.data(), v.length());
	}
	[[nodiscard]] u64 operator()(const char *v) const {
 return fastHash::hash<u64>(v, std::strlen(v));
	}
};

template<>
struct FastHash<std::string_view> : FastHash<std::string> {};
namespace fastHash {
template<typename H>
struct Constants;
template<>
struct Constants<u64> {
	inline static constexpr u64 m{0xC6A4A7935BD1E995u};
	inline static constexpr s32 r{47};
};
template<>
struct Constants<u32> {
	inline static constexpr u32 m{0x5BD1E995u};
	inline static constexpr s32 r{24};
};
template<typename H>
inline constexpr H m{Constants<H>::m};
template<typename H>
inline constexpr s32 r{Constants<H>::r};
template<UnsignedInteger H>
inline constexpr H mix(H v) {
	v *= m<H>;
	v ^= v >> r<H>;
	return v * m<H>;
}
template<UnsignedInteger H, typename T>
inline constexpr H hash(const T &v) {
    	if constexpr(sizeof(T) <= sizeof(H)) {
 return (H(sizeof(T)) * m<H>)^mix(_private::getLowBytes<H>(v));
	}
 	else {
 return hash<H>(&v, sizeof(T));
	}
}

template<UnsignedInteger H>
inline H hash(const void *const data, u64 length) {
	const std::byte *bytes{static_cast<const std::byte *>(data)};
	H h{H(length)};
 	while(length >= sizeof(H)) {
 H w;
 std::memcpy(&w, bytes, sizeof(H));
 h *= m<H>;
 h ^= mix(w);
 bytes += sizeof(H);
 length -= sizeof(H);
	};
 	if(length) {
 H w{0u};
 std::memcpy(&w, bytes, length);
 h *= m<H>;
 h ^= mix(w);
	}
	return h;
}
} template<typename K>
inline RawType<K> &_raw(K &key) {
	return reinterpret_cast<RawType<K> &>(key);
}
template<typename K>
inline const RawType<K> &_raw(const K &key) {
	return reinterpret_cast<const RawType<K> &>(key);
}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A>::RawMap(const u64 capacity, const H &hash,
 const A &alloc)
	: _size{},
 _slotN{capacity <= minMapCapacity ? _private::minMapSlotN
 : std::bit_ceil(capacity << 1)},
 _elements{},
 _haveSpecial{},
 _hash{hash},
 _alloc{alloc} {}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A>::RawMap(const u64 capacity, const A &alloc)
	: RawMap{capacity, H{}, alloc} {}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A>::RawMap(const A &alloc)
	: RawMap{minMapCapacity, H{}, alloc} {}
template<Rawable K, typename V, typename H, typename A>
template<typename It>
inline RawMap<K, V, H, A>::RawMap(const It first, const It last,
 const u64 capacity, const H &hash,
 const A &alloc)
	: RawMap{capacity, hash, alloc} {
 	u64 n{};
	for(It it{first}; it != last; ++it, ++n);
	reserve(n);
	insert(first, last);
}
template<Rawable K, typename V, typename H, typename A>
template<typename It>
inline RawMap<K, V, H, A>::RawMap(const It first, const It last,
 const u64 capacity, const A &alloc)
	: RawMap{first, last, capacity, H{}, alloc} {}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A>::RawMap(const std::initializer_list<E> elements,
 u64 capacity, const H &hash, const A &alloc)
	: RawMap{capacity ? capacity : elements.size(), hash, alloc} {
	insert(elements);
}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A>::RawMap(const std::initializer_list<E> elements,
 const u64 capacity, const A &alloc)
	: RawMap{elements, capacity, H{}, alloc} {}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A>::RawMap(const RawMap &other)
	: _size{other._size},
 _slotN{other._slotN},
 _elements{},
 _haveSpecial{other._haveSpecial[0], other._haveSpecial[1]},
 _hash{other._hash},
 _alloc{std::allocator_traits<A>::select_on_container_copy_construction(
 other._alloc)} {
	if(_size) {
 _allocate<false>();
 _forwardData<false>(other);
	}
}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A>::RawMap(RawMap &&other)
	: _size{std::exchange(other._size, 0u)},
 _slotN{std::exchange(other._slotN, _private::minMapSlotN)},
 _elements{std::exchange(other._elements, nullptr)},
 _haveSpecial{std::exchange(other._haveSpecial[0], false),
 std::exchange(other._haveSpecial[1], false)},
 _hash{std::move(other._hash)},
 _alloc{std::move(other._alloc)} {}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A> &RawMap<K, V, H, A>::operator=(
	const std::initializer_list<E> elements) {
	return *this = RawMap(elements);
}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A> &RawMap<K, V, H, A>::operator=(const RawMap &other) {
	if(&other == this) {
 return *this;
	}
	if(_elements) {
 _clear<false>();
 if(! other._size || _slotN != other._slotN || _alloc != other._alloc) {
 _deallocate();
 }
	}
	_size = other._size;
	_slotN = other._slotN;
	_haveSpecial[0] = other._haveSpecial[0];
	_haveSpecial[1] = other._haveSpecial[1];
	_hash = other._hash;
	if constexpr(std::allocator_traits<
 A>::propagate_on_container_copy_assignment::value) {
 _alloc = std::allocator_traits<A>::select_on_container_copy_construction(
 other._alloc);
	}
	if(_size) {
 if(! _elements) {
 _allocate<false>();
 }
 _forwardData<false>(other);
	}
	return *this;
}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A> &RawMap<K, V, H, A>::operator=(RawMap &&other) {
	if(&other == this) {
 return *this;
	}
	if(_elements) {
 _clear<false>();
 _deallocate();
	}
	_size = other._size;
	_slotN = other._slotN;
	_haveSpecial[0] = other._haveSpecial[0];
	_haveSpecial[1] = other._haveSpecial[1];
	_hash = std::move(other._hash);
	if constexpr(std::allocator_traits<
 A>::propagate_on_container_move_assignment::value) {
 _alloc = std::move(other._alloc);
	}
	if(_alloc == other._alloc
 || std::allocator_traits<
 A>::propagate_on_container_move_assignment::value) {
 _elements = std::exchange(other._elements, nullptr);
 other._size = {};
	} else {
 if(_size) {
 _allocate<false>();
 _forwardData<true>(other);
 other._clear<false>();
 other._size = 0u;
 }
 if(other._elements) {
 other._deallocate();
 }
	}
	other._slotN = _private::minMapSlotN;
	other._haveSpecial[0] = false;
	other._haveSpecial[1] = false;
	return *this;
}
template<Rawable K, typename V, typename H, typename A>
inline RawMap<K, V, H, A>::~RawMap() {
	if(_elements) {
 _clear<false>();
 _deallocate();
	}
}
template<Rawable K, typename V, typename H, typename A>
inline auto RawMap<K, V, H, A>::insert(const E &element)
	-> std::pair<iterator, bool> {
	static_assert(std::is_copy_constructible_v<E>);
	return emplace(element);
}
template<Rawable K, typename V, typename H, typename A>
inline auto RawMap<K, V, H, A>::insert(E &&element)
	-> std::pair<iterator, bool> {
	return emplace(std::move(element));
}
template<Rawable K, typename V, typename H, typename A>
template<typename It>
inline void RawMap<K, V, H, A>::insert(It first, const It last) {
	while(first != last) {
 emplace(*first);
 ++first;
	}
}
template<Rawable K, typename V, typename H, typename A>
inline void RawMap<K, V, H, A>::insert(
	const std::initializer_list<E> elements) {
	for(const E &element : elements) {
 emplace(element);
	}
}
template<Rawable K, typename V, typename H, typename A>
inline auto RawMap<K, V, H, A>::emplace(const E &element)
	-> std::pair<iterator, bool> {
	static_assert(std::is_copy_constructible_v<E>);
	if constexpr(_isSet) {
 return try_emplace(element);
	} else {
 return try_emplace(element.first, element.second);
	}
}
template<Rawable K, typename V, typename H, typename A>
inline auto RawMap<K, V, H, A>::emplace(E &&element)
	-> std::pair<iterator, bool> {
	if constexpr(_isSet) {
 return try_emplace(std::move(element));
	} else {
 return try_emplace(std::move(element.first), std::move(element.second));
	}
}
template<Rawable K, typename V, typename H, typename A>
template<typename K_, typename V_>
inline auto RawMap<K, V, H, A>::emplace(K_ &&key, V_ &&value)
	-> std::pair<iterator, bool>
requires (! std::is_same_v<V, void>)
{
	return try_emplace(std::forward<K_>(key), std::forward<V_>(value));
}
template<Rawable K, typename V, typename H, typename A>
template<typename... KArgs>
inline auto RawMap<K, V, H, A>::emplace(KArgs &&...keyArgs)
	-> std::pair<iterator, bool>
requires (std::is_same_v<V, void>)
{
	return try_emplace(K{std::forward<KArgs>(keyArgs)...});
}
template<Rawable K, typename V, typename H, typename A>
template<typename... KArgs, typename... VArgs>
inline auto RawMap<K, V, H, A>::emplace(const std::piecewise_construct_t,
 std::tuple<KArgs...> &&keyArgs,
 std::tuple<VArgs...> &&valueArgs)
	-> std::pair<iterator, bool>
requires (! std::is_same_v<V, void>)
{
	return _emplace(std::move(keyArgs), std::move(valueArgs),
 std::index_sequence_for<KArgs...>(),
 std::index_sequence_for<VArgs...>());
}
template<Rawable K, typename V, typename H, typename A>
template<typename KTuple, typename VTuple, u64... kIndices, u64... vIndices>
inline auto RawMap<K, V, H, A>::_emplace(KTuple &&kTuple, VTuple &&vTuple,
 const std::index_sequence<kIndices...>,
 const std::index_sequence<vIndices...>)
	-> std::pair<iterator, bool> {
	return try_emplace(K{std::move(std::get<kIndices>(kTuple))...},
 std::move(std::get<vIndices>(vTuple))...);
}
template<Rawable K, typename V, typename H, typename A>
template<typename K_, typename... VArgs>
inline auto RawMap<K, V, H, A>::try_emplace(K_ &&key, VArgs &&...vArgs)
	-> std::pair<iterator, bool> {
	static_assert(
 ! (_isMap && ! sizeof...(VArgs) && ! std::is_default_constructible_v<V>),
 "The value type must be default constructible in order to pass no value "
 "arguments");
	static_assert(! (_isSet && sizeof...(VArgs)), "Sets do not have values");
 	if(! _elements) {
 _allocate<true>();
	}
	_FindKeyResult<true> findResult{_findKey<true>(key)};
 	if(findResult.isPresent) {
 return {iterator{findResult.element}, false};
	}
	if(findResult.isSpecial) [[unlikely]] {
 _haveSpecial[findResult.specialI] = true;
	} else {
  if((_size - _haveSpecial[0] - _haveSpecial[1]) >= (_slotN >> 1))
 [[unlikely]] {
 _rehash(_slotN << 1);
 findResult = _findKey<true>(key);
 }
	}
	if constexpr(_isSet) {
 std::allocator_traits<A>::construct(_alloc, findResult.element,
 std::forward<K_>(key));
	} else {
 std::allocator_traits<A>::construct(_alloc, &findResult.element->first,
 std::forward<K_>(key));
 std::allocator_traits<A>::construct(_alloc, &findResult.element->second,
 std::forward<VArgs>(vArgs)...);
	}
	++_size;
	return {iterator{findResult.element}, true};
}
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline bool RawMap<K, V, H, A>::erase(const K_ &key) {
	if(! _size) {
 return false;
	}
	const auto [element, isPresent]{_findKey<false>(key)};
	if(isPresent) {
 erase(iterator{element});
 return true;
	} else {
 return false;
	}
}
template<Rawable K, typename V, typename H, typename A>
inline void RawMap<K, V, H, A>::erase(const iterator position) {
	E *const eraseElement{position._element};
	_RawKey &rawKey{_raw(_key(*eraseElement))};
	E *const specialElements{_elements + _slotN};
	std::allocator_traits<A>::destroy(_alloc, eraseElement);
 	if(eraseElement < specialElements) {
 rawKey = _graveKey;
	} else [[unlikely]] {
 const auto specialI{eraseElement - specialElements};
 _raw(_key(specialElements[specialI])) = _vacantSpecialKeys[specialI];
 _haveSpecial[specialI] = false;
	}
	--_size;
}
template<Rawable K, typename V, typename H, typename A>
inline void RawMap<K, V, H, A>::clear() {
	_clear<true>();
}
template<Rawable K, typename V, typename H, typename A>
template<bool preserveInvariants>
inline void RawMap<K, V, H, A>::_clear() {
	if constexpr(std::is_trivially_destructible_v<E>) {
 if constexpr(preserveInvariants) {
 if(_size) {
 _clearKeys();
 _size = {};
 _haveSpecial[0] = false;
 _haveSpecial[1] = false;
 }
 }
	} else {
 if(_size) {
  E *element{_elements};
 u64 n{};
 const u64 regularElementN{_size - _haveSpecial[0] - _haveSpecial[1]};
 for(; n < regularElementN; ++element) {
 _RawKey &rawKey{_raw(_key(*element))};
 if(_isPresent(rawKey)) {
 std::allocator_traits<A>::destroy(_alloc, element);
 ++n;
 }
 if constexpr(preserveInvariants) {
 rawKey = _vacantKey;
 }
 }
  if constexpr(preserveInvariants) {
 const E *const endRegularElement{_elements + _slotN};
 for(; element < endRegularElement; ++element) {
 _raw(_key(*element)) = _vacantKey;
 }
 }
  if(_haveSpecial[0]) [[unlikely]] {
 element = _elements + _slotN;
 std::allocator_traits<A>::destroy(_alloc, element);
 if constexpr(preserveInvariants) {
 _raw(_key(*element)) = _vacantGraveKey;
 _haveSpecial[0] = false;
 }
 }
 if(_haveSpecial[1]) [[unlikely]] {
 element = _elements + _slotN + 1;
 std::allocator_traits<A>::destroy(_alloc, element);
 if constexpr(preserveInvariants) {
 _raw(_key(*element)) = _vacantVacantKey;
 _haveSpecial[1] = false;
 }
 }
 if constexpr(preserveInvariants) {
 _size = {};
 }
 }
	}
}
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline bool RawMap<K, V, H, A>::contains(const K_ &key) const {
	return _size ? _findKey<false>(key).isPresent : false;
}
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline u64 RawMap<K, V, H, A>::count(const K_ &key) const {
	return contains(key);
}
#ifdef QC_HASH_EXCEPTIONS_ENABLED
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline std::add_lvalue_reference_t<V> RawMap<K, V, H, A>::at(const K_ &key)
requires (! std::is_same_v<V, void>)
{
	return const_cast<V &>(static_cast<const RawMap *>(this)->at(key));
}
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline std::add_lvalue_reference_t<const V> RawMap<K, V, H, A>::at(
	const K_ &key) const
requires (! std::is_same_v<V, void>)
{
	if(! _size) {
 throw std::out_of_range{"Map is empty"};
	}
	const auto [element, isPresent]{_findKey<false>(key)};
	if(! isPresent) {
 throw std::out_of_range{"Element not found"};
	}
	return element->second;
}
#endif
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline std::add_lvalue_reference_t<V> RawMap<K, V, H, A>::operator[](
	const K_ &key)
requires (! std::is_same_v<V, void>)
{
	return try_emplace(key).first->second;
}
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline std::add_lvalue_reference_t<V> RawMap<K, V, H, A>::operator[](K_ &&key)
requires (! std::is_same_v<V, void>)
{
	return try_emplace(std::move(key)).first->second;
}
template<Rawable K, typename V, typename H, typename A>
inline auto RawMap<K, V, H, A>::begin() -> iterator {
	return const_cast<E *>(static_cast<const RawMap *>(this)->begin()._element);
}
template<Rawable K, typename V, typename H, typename A>
inline auto RawMap<K, V, H, A>::begin() const -> const_iterator {
 	if(_size - _haveSpecial[0] - _haveSpecial[1]) [[likely]] {
 for(const E *element{_elements};; ++element) {
 if(_isPresent(_raw(_key(*element)))) {
 return const_iterator{element};
 }
 }
	}
 	if(_haveSpecial[0]) [[unlikely]] {
 return const_iterator{_elements + _slotN};
	}
	if(_haveSpecial[1]) [[unlikely]] {
 return const_iterator{_elements + _slotN + 1};
	}
	return end();
}
template<Rawable K, typename V, typename H, typename A>
inline auto RawMap<K, V, H, A>::cbegin() const -> const_iterator {
	return begin();
}
template<Rawable K, typename V, typename H, typename A>
inline typename RawMap<K, V, H, A>::iterator RawMap<K, V, H, A>::end() {
	return iterator{};
}
template<Rawable K, typename V, typename H, typename A>
inline auto RawMap<K, V, H, A>::end() const -> const_iterator {
	return const_iterator{};
}
template<Rawable K, typename V, typename H, typename A>
inline auto RawMap<K, V, H, A>::cend() const -> const_iterator {
	return const_iterator{};
}
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline auto RawMap<K, V, H, A>::find(const K_ &key) -> iterator {
	return const_cast<E *>(static_cast<const RawMap *>(this)->find(key)._element);
}
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline auto RawMap<K, V, H, A>::find(const K_ &key) const -> const_iterator {
	if(! _size) {
 return cend();
	}
	const auto [element, isPresent]{_findKey<false>(key)};
	return isPresent ? const_iterator{element} : cend();
}
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline u64 RawMap<K, V, H, A>::slot(const K_ &key) const {
	const _RawKey &rawKey{_raw(key)};
	if(_isSpecial(rawKey)) [[unlikely]] {
 return _slotN + (rawKey == _vacantKey);
	} else {
 return _slot(key);
	}
}
template<Rawable K, typename V, typename H, typename A>
template<Compatible<K> K_>
inline u64 RawMap<K, V, H, A>::_slot(const K_ &key) const {
	return _hash(key) & (_slotN - 1u);
}
template<Rawable K, typename V, typename H, typename A>
inline void RawMap<K, V, H, A>::reserve(const u64 capacity) {
	rehash(capacity << 1);
}
template<Rawable K, typename V, typename H, typename A>
inline void RawMap<K, V, H, A>::rehash(u64 slotN) {
	const u64 currentMinSlotN{
 _size <= minMapCapacity
 ? _private::minMapSlotN
 : ((_size - _haveSpecial[0] - _haveSpecial[1]) << 1)};
	if(slotN < currentMinSlotN) {
 slotN = currentMinSlotN;
	} else {
 slotN = std::bit_ceil(slotN);
	}
	if(slotN != _slotN) {
 if(_elements) {
 _rehash(slotN);
 } else {
 _slotN = slotN;
 }
	}
}
template<Rawable K, typename V, typename H, typename A>
inline void RawMap<K, V, H, A>::_rehash(const u64 slotN) {
	const u64 oldSize{_size};
	const u64 oldSlotN{_slotN};
	E *const oldElements{_elements};
	const bool oldHaveSpecial[2]{_haveSpecial[0], _haveSpecial[1]};
	_size = {};
	_slotN = slotN;
	_allocate<true>();
	_haveSpecial[0] = false;
	_haveSpecial[1] = false;
 	u64 n{};
	const u64 regularElementN{oldSize - oldHaveSpecial[0] - oldHaveSpecial[1]};
	for(E *element{oldElements}; n < regularElementN; ++element) {
 if(_isPresent(_raw(_key(*element)))) {
 emplace(std::move(*element));
 std::allocator_traits<A>::destroy(_alloc, element);
 ++n;
 }
	}
 	if(oldHaveSpecial[0]) [[unlikely]] {
 E *const oldElement{oldElements + oldSlotN};
 std::allocator_traits<A>::construct(_alloc, _elements + _slotN,
 std::move(*oldElement));
 std::allocator_traits<A>::destroy(_alloc, oldElement);
 ++_size;
 _haveSpecial[0] = true;
	}
	if(oldHaveSpecial[1]) [[unlikely]] {
 E *const oldElement{oldElements + oldSlotN + 1};
 std::allocator_traits<A>::construct(_alloc, _elements + _slotN + 1,
 std::move(*oldElement));
 std::allocator_traits<A>::destroy(_alloc, oldElement);
 ++_size;
 _haveSpecial[1] = true;
	}
	std::allocator_traits<A>::deallocate(_alloc, oldElements, oldSlotN + 4u);
}
template<Rawable K, typename V, typename H, typename A>
inline void RawMap<K, V, H, A>::swap(RawMap &other) {
	std::swap(_size, other._size);
	std::swap(_slotN, other._slotN);
	std::swap(_elements, other._elements);
	std::swap(_haveSpecial, other._haveSpecial);
	std::swap(_hash, other._hash);
	if constexpr(std::allocator_traits<A>::propagate_on_container_swap::value) {
 std::swap(_alloc, other._alloc);
	}
}
template<Rawable K, typename V, typename H, typename A>
inline u64 RawMap<K, V, H, A>::size() const {
	return _size;
}
template<Rawable K, typename V, typename H, typename A>
inline bool RawMap<K, V, H, A>::empty() const {
	return ! _size;
}
template<Rawable K, typename V, typename H, typename A>
inline u64 RawMap<K, V, H, A>::capacity() const {
	return _slotN >> 1;
}
template<Rawable K, typename V, typename H, typename A>
inline u64 RawMap<K, V, H, A>::slot_n() const {
	return _slotN;
}
template<Rawable K, typename V, typename H, typename A>
inline u64 RawMap<K, V, H, A>::max_size() const {
	return (max_slot_n() >> 1) + 2u;
}
template<Rawable K, typename V, typename H, typename A>
inline u64 RawMap<K, V, H, A>::max_slot_n() const {
	return u64{1u} << 63;
}
template<Rawable K, typename V, typename H, typename A>
inline f32 RawMap<K, V, H, A>::load_factor() const {
	return f32(_size) / f32(_slotN);
}
template<Rawable K, typename V, typename H, typename A>
inline f32 RawMap<K, V, H, A>::max_load_factor() const {
	return f32(minMapCapacity) / f32(_private::minMapSlotN);
}
template<Rawable K, typename V, typename H, typename A>
inline const H &RawMap<K, V, H, A>::hash_function() const {
	return _hash;
}
template<Rawable K, typename V, typename H, typename A>
inline const A &RawMap<K, V, H, A>::get_allocator() const {
	return _alloc;
}
template<Rawable K, typename V, typename H, typename A>
inline K &RawMap<K, V, H, A>::_key(E &element) {
	if constexpr(_isSet)
 return element;
	else
 return element.first;
}
template<Rawable K, typename V, typename H, typename A>
inline const K &RawMap<K, V, H, A>::_key(const E &element) {
	if constexpr(_isSet)
 return element;
	else
 return element.first;
}
template<Rawable K, typename V, typename H, typename A>
inline bool RawMap<K, V, H, A>::_isPresent(const _RawKey &key) {
	return ! _isSpecial(key);
}
template<Rawable K, typename V, typename H, typename A>
inline bool RawMap<K, V, H, A>::_isSpecial(const _RawKey &key) {
	return key == _vacantKey || key == _graveKey;
}
template<Rawable K, typename V, typename H, typename A>
template<bool zeroKeys>
inline void RawMap<K, V, H, A>::_allocate() {
	_elements = std::allocator_traits<A>::allocate(_alloc, _slotN + 4u);
	if constexpr(zeroKeys) {
 _clearKeys();
	}
  	_raw(_key(_elements[_slotN + 2])) = _terminalKey;
	_raw(_key(_elements[_slotN + 3])) = _terminalKey;
}
template<Rawable K, typename V, typename H, typename A>
inline void RawMap<K, V, H, A>::_deallocate() {
	std::allocator_traits<A>::deallocate(_alloc, _elements, _slotN + 4u);
	_elements = nullptr;
}
template<Rawable K, typename V, typename H, typename A>
inline void RawMap<K, V, H, A>::_clearKeys() {
 	E *const specialElements{_elements + _slotN};
	for(E *element{_elements}; element < specialElements; ++element) {
 _raw(_key(*element)) = _vacantKey;
	}
 	_raw(_key(specialElements[0])) = _vacantGraveKey;
	_raw(_key(specialElements[1])) = _vacantVacantKey;
}
template<Rawable K, typename V, typename H, typename A>
template<bool move>
inline void RawMap<K, V, H, A>::_forwardData(
	std::conditional_t<move, RawMap, const RawMap> &other) {
	if constexpr(std::is_trivially_copyable_v<E>) {
 std::memcpy(_elements, other._elements, (_slotN + 2u) * sizeof(E));
	} else {
 using ElementForwardType = std::conditional_t<move, E &&, const E &>;
  std::conditional_t<move, E, const E> *srcElement{other._elements};
 const E *const srcEndElement{other._elements + _slotN};
 E *dstElement{_elements};
 for(; srcElement < srcEndElement; ++srcElement, ++dstElement) {
 const _RawKey &rawSrcKey{_raw(_key(*srcElement))};
 if(_isPresent(rawSrcKey)) {
 std::allocator_traits<A>::construct(
 _alloc, dstElement, static_cast<ElementForwardType>(*srcElement));
 } else {
 _raw(_key(*dstElement)) = rawSrcKey;
 }
 }
  if(_haveSpecial[0]) {
 std::allocator_traits<A>::construct(
 _alloc, _elements + _slotN,
 static_cast<ElementForwardType>(other._elements[_slotN]));
 } else {
 _raw(_key(_elements[_slotN])) = _vacantGraveKey;
 }
 if(_haveSpecial[1]) {
 std::allocator_traits<A>::construct(
 _alloc, _elements + _slotN + 1,
 static_cast<ElementForwardType>(other._elements[_slotN + 1]));
 } else {
 _raw(_key(_elements[_slotN + 1])) = _vacantVacantKey;
 }
	}
}
template<Rawable K, typename V, typename H, typename A>
template<bool insertionForm, Compatible<K> K_>
inline auto RawMap<K, V, H, A>::_findKey(const K_ &key) const
	-> _FindKeyResult<insertionForm> {
	const _RawKey &rawKey{_raw(key)};
 	if(_isSpecial(rawKey)) [[unlikely]] {
 const unsigned char specialI{rawKey == _vacantKey};
 if constexpr(insertionForm) {
 return _FindKeyResult<insertionForm>{
 .element = _elements + _slotN + specialI,
 .isPresent = _haveSpecial[specialI],
 .isSpecial = true,
 .specialI = specialI};
 } else {
 return _FindKeyResult<insertionForm>{
 .element = _elements + _slotN + specialI,
 .isPresent = _haveSpecial[specialI]};
 }
	}
 	const E *const lastElement{_elements + _slotN};
	E *element{_elements + _slot(key)};
	E *grave{};
	while(true) {
 const _RawKey &rawSlotKey{_raw(_key(*element))};
 if(rawSlotKey == rawKey) {
 if constexpr(insertionForm) {
 return {.element = element,
 .isPresent = true,
 .isSpecial = false,
 .specialI = 0u};
 } else {
 return {.element = element, .isPresent = true};
 }
 }
 if(rawSlotKey == _vacantKey) {
 if constexpr(insertionForm) {
 return {.element = grave ? grave : element,
 .isPresent = false,
 .isSpecial = false,
 .specialI = 0u};
 } else {
 return {.element = element, .isPresent = false};
 }
 }
 if constexpr(insertionForm) {
 if(rawSlotKey == _graveKey) {
 grave = element;
 }
 }
 ++element;
 if(element == lastElement) [[unlikely]] {
 element = _elements;
 }
	}
}
template<Rawable K, typename V, typename H, typename A>
inline bool operator==(const RawMap<K, V, H, A> &m1,
 const RawMap<K, V, H, A> &m2) {
	if(m1.size() != m2.size()) {
 return false;
	}
	if(&m1 == &m2) {
 return true;
	}
	const auto endIt{m2.cend()};
	for(const auto &element : m1) {
 if constexpr(std::is_same_v<V, void>) {
 if(! m2.contains(element)) {
 return false;
 }
 } else {
 const auto it{m2.find(element.first)};
 if(it == endIt || it->second != element.second) {
 return false;
 }
 }
	}
	return true;
}
template<Rawable K, typename V, typename H, typename A>
template<bool constant>
template<bool constant_>
requires (constant && ! constant_)
inline constexpr RawMap<K, V, H, A>::_Iterator<constant>::_Iterator(
	const _Iterator<constant_> &other)
	: _element{other._element} {}
template<Rawable K, typename V, typename H, typename A>
template<bool constant>
inline constexpr RawMap<K, V, H, A>::_Iterator<constant>::_Iterator(
	E *const element)
	: _element{element} {}
template<Rawable K, typename V, typename H, typename A>
template<bool constant>
template<bool constant_>
requires (constant && ! constant_)
inline auto RawMap<K, V, H, A>::_Iterator<constant>::operator=(
	const _Iterator<constant_> &other) -> _Iterator & {
	_element = other._element;
	return *this;
}
template<Rawable K, typename V, typename H, typename A>
template<bool constant>
inline auto RawMap<K, V, H, A>::_Iterator<constant>::operator*() const -> E & {
	return *_element;
}
template<Rawable K, typename V, typename H, typename A>
template<bool constant>
inline auto RawMap<K, V, H, A>::_Iterator<constant>::operator->() const -> E * {
	return _element;
}
template<Rawable K, typename V, typename H, typename A>
template<bool constant>
inline auto RawMap<K, V, H, A>::_Iterator<constant>::operator++()
	-> _Iterator & {
	while(true) {
 ++_element;
 const _RawKey &rawKey{_raw(_key(*_element))};
  if(_isPresent(rawKey)) {
 if(rawKey == _terminalKey) [[unlikely]] {
  if(_raw(_key(_element[1])) == _terminalKey) {
 _element = nullptr;
 }
 }
 return *this;
 }
  if(_raw(_key(_element[2])) == _terminalKey) [[unlikely]] {
  if(_raw(_key(_element[1])) == _terminalKey) [[unlikely]] {
 if(rawKey == _vacantVacantKey) [[likely]] {
 _element = nullptr;
 }
 return *this;
 }
  if(_raw(_key(_element[3])) == _terminalKey) [[likely]] {
 if(rawKey == _vacantGraveKey) [[likely]] {
 if(_raw(_key(_element[1])) == _vacantVacantKey) [[likely]] {
 _element = nullptr;
 } else {
 ++_element;
 }
 }
 return *this;
 }
 }
	}
}
template<Rawable K, typename V, typename H, typename A>
template<bool constant>
inline auto RawMap<K, V, H, A>::_Iterator<constant>::operator++(int)
	-> _Iterator {
	const _Iterator temp{*this};
	operator++();
	return temp;
}
template<Rawable K, typename V, typename H, typename A>
template<bool constant>
template<bool constant_>
inline bool RawMap<K, V, H, A>::_Iterator<constant>::operator==(
	const _Iterator<constant_> &other) const {
	return _element == other._element;
}
} namespace std {
template<typename K, typename V, typename H, typename A>
inline void swap(qc::hash::RawMap<K, V, H, A> &a,
 qc::hash::RawMap<K, V, H, A> &b) {
	a.swap(b);
}
}
#define MOD_IS_998 1
#if __has_include("template.hpp")
#include "template.hpp"
#else

#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstdint>
#include <functional>
#include <ios>
#include <iostream>
#include <istream>
#include <limits>
#include <map>
#include <ostream>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <utility>
#include <vector>
#include <version>
#include <atcoder/modint.hpp>
using namespace std;
using ll = long long;
using pall = pair<ll, ll>;
template<class T>
using vec = vector<T>;
template<class T>
using veve = vec<vec<T>>;
using vell = vec<ll>;
using vest = vec<string>;
using vebo = basic_string<bool>;
using vevell = veve<ll>;
template<class T>
using mset = multiset<T>;
template<class T>
using priority_queue_ascend = priority_queue<T, vec<T>, greater<T>>;
constexpr ll inf = numeric_limits<ll>::max();
const string sp = " ";
const string lf = "\n";
const auto &npos = string::npos;
#ifdef MOD_IS_998
constexpr ll MOD = 998244353;
#else
constexpr ll MOD = 1e9 + 7;
#endif
const vec<pall> grid_move4 = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
const vec<pall> grid_move8 = [] {
	auto ret = grid_move4;
	ret.insert(ret.end(), {{-1, 1}, {-1, -1}, {1, -1}, {1, 1}});
	return ret;
}();
#define cont continue
#define br break
#define whlie while
#define foR for
#define reutnr return
#define retunr return
#define reutrn return
#define auot auto
#define uato auto
#define cosnt const
#define conts const
#define ocnst const
auto &ciN = cin;
auto &icn = cin;
auto &icN = cin;
constexpr bool ture = true;
constexpr bool flase = false;
namespace rnages = ranges;
namespace ra = ranges;
using namespace atcoder;
using mint = static_modint<MOD>;
#define times(N) \
	static_assert(is_integral_v<decltype((N) + 0)>, \
 "times(): N must be integral"); \
	assert((N) >= 0); \
	for(typedef decltype((N) + 0) _int; \
 [[maybe_unused]] const _int _i : views::iota((_int)0, (N)))
#define tiems times
#define itmes times
template<int M>
istream &operator>>(istream &in, static_modint<M> &i) {
	ll tmp;
	in >> tmp;
	i = tmp;
	return in;
}
template<int M>
ostream &operator<<(ostream &out, const static_modint<M> &i) {
	return out << i.val();
}
template<class T, class U>
istream &operator>>(istream &in, pair<T, U> &p) {
	return in >> p.first >> p.second;
}
template<class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &p) {
	return out << p.first << sp << p.second;
}
template<class T>
istream &operator>>(istream &in, vec<T> &v) {
	for(auto &&e : v) {
 in >> e;
	}
	return in;
}
struct debug_stream {
	template<class T>
	debug_stream &operator<<([[maybe_unused]] const T &x) {
#ifndef ONLINE_JUDGE
 clog << x;
#endif
 return *this;
	}
	debug_stream &operator<<([[maybe_unused]] ostream &(*f)(ostream &)) {
#ifndef ONLINE_JUDGE
 clog << f;
#endif
 return *this;
	}
};
template<class T>
concept out_stream = same_as<ostream, T> || same_as<debug_stream, T>;
debug_stream clog_;
#define clog clog_
template<class... Ts>
istream &in(Ts &...vecs) {
	static_assert(sizeof...(vecs) != 0,
 "myfunc::in(): At least one vector must be provided");
	const set sizes = {vecs.size()...};
	if(sizes.size() > 1) {
 throw invalid_argument("myfunc::in(): All vectors must have the same size");
	}
	times(*sizes.begin()) {
 ((cin >> vecs[_i]), ...);
	}
	return cin;
}
void out(ranges::range auto v, const string delim, out_stream auto &out) {
	ranges::for_each(v, [&](const auto &e) { out << e << delim; });
}
void out(ranges::range auto v, const string delim) {
	out(v, delim, cout);
}
[[nodiscard]] const string &yesno(const bool cond, const string &yes = "Yes",
 const string &no = "No") noexcept {
	if(cond) return yes;
	return no;
}

[[nodiscard]] uint64_t randint(const uint64_t mi, const uint64_t ma) noexcept {
	static random_device seed;
	static mt19937_64 mt(seed());
	if(mi > ma) [[unlikely]]
 return randint(ma, mi);
	if(mi == ma) [[unlikely]]
 return mi;
	const uint64_t w = ma - mi;
	uint64_t r;
	do {
 r = mt();
	} while(mt.max() - mt.max() % w <= r);
	return r % w + mi;
}
template<class T, class U>
requires common_with<T, U>
[[nodiscard]] constexpr auto min(T &&a, U &&b) noexcept {
	return std::min<common_type_t<T, U>>(std::forward<T>(a), std::forward<U>(b));
}
template<class T, class U>
requires common_with<T, U>
[[nodiscard]] constexpr auto max(T &&a, U &&b) noexcept {
	return std::max<common_type_t<T, U>>(std::forward<T>(a), std::forward<U>(b));
}
template<class... Args>
[[nodiscard]] auto reduce(const ranges::range auto &r, Args &&...args) {
	return reduce(ranges::cbegin(r), ranges::cend(r), forward<Args>(args)...);
}
[[nodiscard]] constexpr ll powll(ll a, ll b, const ll m = inf) {
	if(b < 0) [[unlikely]]
 throw invalid_argument("powll(): exponent less than zero");
	if(m < 1) [[unlikely]]
 throw invalid_argument("powll(): modulo less than one");
	a %= m;
	ll ret = 1;
	while(b) {
 if(b % 2) ret *= a, ret %= m;
 a *= a, a %= m;
 b /= 2;
	}
	return ret;
}
template<class T, class U>
requires assignable_from<T &, U> && totally_ordered_with<T, U>
bool mini(T &var, U &&val) noexcept {
	const bool cmp = var > val;
	if(cmp) var = val;
	return cmp;
}
template<class T, class U>
requires assignable_from<T &, U> && totally_ordered_with<T, U>
bool maxi(T &var, U &&val) noexcept {
	const bool cmp = var < val;
	if(cmp) var = val;
	return cmp;
}
class [[nodiscard]] grid_base {
	public:
	grid_base(const ll h, const ll w) noexcept : height(h), width(w) {}
	[[nodiscard]] ll operator()(const ll i, const ll j) const noexcept {
 if(! isvalid(i, j)) return -1;
 return i * width + j;
	}
	[[nodiscard]] ll operator()(const pall &p) const noexcept {
 return (*this)(p.first, p.second);
	}
	protected:
	bool isvalid(const ll i, const ll j) const noexcept {
 return 0 <= i && 0 <= j && i < height && j < width;
	}
	const ll height, width;
};
class [[nodiscard]] grid_seen : public grid_base {
	public:
	grid_seen(const ll h, const ll w) : grid_base(h, w) {
 visited = vebo(h * w, false);
	}
	[[nodiscard]] bool &seen(const ll i, const ll j) & {
 if(! isvalid(i, j)) [[unlikely]]
 throw out_of_range("grid_seen::seen(): out of range");
 return visited[i * width + j];
	}
	[[nodiscard]] bool &sen(const ll i, const ll j) & {
 return seen(i, j);
	}
	[[nodiscard]] bool &seen(const pall &p) & {
 return seen(p.first, p.second);
	}
	[[nodiscard]] bool &sen(const pall &p) & {
 return seen(p);
	}
	private:
	vebo visited;
};
using grid_lite = grid_base;
template<auto defval, class... Args>
requires is_convertible_v<decltype(defval), typename map<Args...>::mapped_type>
class default_map : public map<Args...> {
	using Map = map<Args...>;
	public:
#ifdef __cpp_lib_associative_heterogeneous_insertion
	template<convertible_to<typename Map::key_type> U>
	requires requires(Map::key_compare c, Map::key_type t, U u) {
 c(t, u);
 c(u, t);
	}
	Map::mapped_type &operator[](const U &key) {
 Map::try_emplace(key, defval);
 return Map::operator[](key);
	}
	template<convertible_to<typename Map::key_type> U>
	requires requires(Map::key_compare c, Map::key_type t, U u) {
 c(t, u);
 c(u, t);
	}
	Map::mapped_type &operator[](const U &&key) {
 Map::try_emplace(key, defval);
 return Map::operator[](key);
	}
#else
	Map::mapped_type &operator[](const Map::key_type &key) {
 Map::try_emplace(key, defval);
 return Map::operator[](key);
	}
	Map::mapped_type &operator[](const Map::key_type &&key) {
 Map::try_emplace(key, defval);
 return Map::operator[](key);
	}
#endif
};
template<auto defval, class... Args>
requires is_convertible_v<decltype(defval),
 typename unordered_map<Args...>::mapped_type>
class default_unordered_map : public unordered_map<Args...> {
	using Map = unordered_map<Args...>;
	public:
#ifdef __cpp_lib_associative_heterogeneous_insertion
	template<class U>
	requires requires(Map::hasher h, U u) { h(u); }
	Map::mapped_type &operator[](const U &key) {
 Map::try_emplace(key, defval);
 return Map::operator[](key);
	}
	template<class U>
	requires requires(Map::hasher h, U u) { h(u); }
	Map::mapped_type &operator[](const U &&key) {
 Map::try_emplace(key, defval);
 return Map::operator[](key);
	}
#else
	Map::mapped_type &operator[](const Map::key_type &key) {
 Map::try_emplace(key, defval);
 return Map::operator[](key);
	}
	Map::mapped_type &operator[](const Map::key_type &&key) {
 Map::try_emplace(key, defval);
 return Map::operator[](key);
	}
#endif
};
template<class T, class U>
requires requires(mset<T>::key_compare c, T t, U u) { c(t, u); }
auto erase_single(mset<T> &mset, U &&v) {
	const auto it = mset.find(v);
	if(it == mset.end()) [[unlikely]]
 throw invalid_argument("erase_single(): why v not in mset!?!?");
	return mset.erase(it);
}
void solve();

#endif
int main(void) {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	ll t = 1;
 	times(t) solve();
	return 0;
}
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <vector>
using namespace std;
using ll = long long;


class linear_sieve {
	public:
	linear_sieve(const ll n) {
 minfactor.resize(n + 1, 0);
 minfactor[0] = 0;
 minfactor[1] = 1;
 primes.reserve(ll(n / log(n) * 1.15));
 for(ll i = 2; i <= n; i++) {
 if(! minfactor[i]) minfactor[i] = i, primes.push_back(i);
 for(size_t j = 0; j != primes.size() && primes[j] <= minfactor[i]; j++) {
 if(i * primes[j] > n) break;
 minfactor[i * primes[j]] = primes[j];
 }
 }
	}
	vector<ll> minfactor, primes;
};


class segment_sieve : public linear_sieve {
	public:
	segment_sieve(const ll l, const ll r) : linear_sieve((ll)sqrt(r) + 10) {
 isprime = vector<bool>(r - l + 1, true);
 for(const auto &p : primes) {
 ll cur = max(p * p, (l + p - 1) / p * p) - l;
 for(; cur < r - l + 1; cur += p) {
 isprime[cur] = false;
 }
 }
	}
	vector<bool> isprime;
};
void solve() {
	const auto lpf = linear_sieve(1e6 + 10).minfactor;
	ll n;
	cin >> n;
	vell a(n);
	cin >> a;
	vevell nei(n);
	times(n - 1) {
 ll u, v;
 cin >> u >> v;
 u--, v--;
 nei[u].push_back(v);
 nei[v].push_back(u);
	}
	vec<mint> ans(n);
	vebo sen(n, false);
	const auto dfs = [&](auot &&self, const ll i) -> qc::hash::RawMap<ll, ll> {
 sen[i] = ture;
 qc::hash::RawMap<ll, ll> m;
 mint mp = a[i];
 {
 ll tmp = a[i];
 while(tmp != 1) {
 m[lpf[tmp]]++;
 tmp /= lpf[tmp];
 }
 }
 clog << "in v" << i << lf;
 for(const auot &e : nei[i]) {
 if(sen[e]) cont;
 auto m2 = self(self, e);
 if(m.size() < m2.size()) {
 swap(m, m2);
 mp = ans[e];
 }
 clog << "mp: " << mp << lf;
 clog << "m: ";
 out(m, sp, clog), clog << lf;
 clog << "m2: ";
 out(m2, sp, clog), clog << lf;
 for(const auto &[p, e] : m2) {
 if(m.contains(p) && m[p] >= e) cont;
 mp *= mint(p).pow(e - m[p]);
 m[p] = e;
 }
 clog << "mp: " << mp << lf;
 clog << "m: ";
 out(m, sp, clog), clog << lf;
 }
 ans[i] = mp;
 retunr m;
	};
	dfs(dfs, 0);
	out(ans, lf);
}

yukicoder

結果

コンパイルメッセージ

ソースコード