k乗根(整数)
(C++/math/kthrooti.hpp)

• View this file on GitHub
• Last update: 2024-02-19 12:20:55+09:00
• Include: #include "C++/math/kthrooti.hpp"

Required by

• 素数の個数 (C++/math/primecounter.hpp)
• テンプレート (C++/template.hpp)

Verified with

• test/aarray.test.cpp
• test/add.test.cpp
• test/add128.test.cpp
• test/extgcd.test.cpp
• test/fwtree.test.cpp
• test/kthrooti.test.cpp
• test/m_add.test.cpp
• test/parsum.test.cpp
• test/pcounter.test.cpp
• test/s_rmq.test.cpp
• test/segtree.test.cpp
• test/sr_sum.test.cpp
• test/stable.test.cpp
• test/uf.test.cpp

Code

#pragma once

#include <limits>
#ifndef TEMPLATE
typedef unsigned long long ul;
template <class T, class U> inline bool overflow_if_mul(const T a, const U b){ return (std::numeric_limits<T>::max()/a)<b; }
#endif
namespace Heileden {
inline ul kthrooti(const ul n, const int k) {
    if(k==1) {
		return n;
	}
	const auto chk=[&](const unsigned x) {
		ul mul=1;
		for(int i = 0; i < k; ++i) {
            if(overflow_if_mul(mul, x)) {
                return false;
            }
            mul*=x;
        }
		return mul<=n;
	};
	ul ret=0;
	for(int i = 32; --i >= 0;) {
		if(chk(ret|(1U<<i))) {
			ret|=1U<<i;
		}
	}
	return ret;
}
}

/**
 * @brief k乗根(整数)
 */

#line 2 "C++/math/kthrooti.hpp"

#include <limits>
#ifndef TEMPLATE
typedef unsigned long long ul;
template <class T, class U> inline bool overflow_if_mul(const T a, const U b){ return (std::numeric_limits<T>::max()/a)<b; }
#endif
namespace Heileden {
inline ul kthrooti(const ul n, const int k) {
    if(k==1) {
		return n;
	}
	const auto chk=[&](const unsigned x) {
		ul mul=1;
		for(int i = 0; i < k; ++i) {
            if(overflow_if_mul(mul, x)) {
                return false;
            }
            mul*=x;
        }
		return mul<=n;
	};
	ul ret=0;
	for(int i = 32; --i >= 0;) {
		if(chk(ret|(1U<<i))) {
			ret|=1U<<i;
		}
	}
	return ret;
}
}

/**
 * @brief k乗根(整数)
 */

Back to top page