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

floor K 乗根
(math/iroot.hpp)

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

floor K 乗根

使い方

ll iroot(ll n, ll k=2) : $\lfloor \sqrt[k]{n} \rfloor$ を求める（ $k$ のデフォルトは $2$ ）

Required by

• $n$ 以下の素数の数え上げ (math/counting_primes.hpp)
• discrete_logarithm (math/discrete_logarithm.hpp)

Verified with

• verify/yosupo/counting_primes.test.cpp
• verify/yosupo/discrete_logarithm.test.cpp
• verify/yosupo/kth_root_integer.test.cpp
• verify/yukicoder/1661.test.cpp

Code

#pragma once

#include<cmath>
#include<limits>

unsigned long long iroot(unsigned long long n, int k=2){
	constexpr unsigned long long LIM = std::numeric_limits<unsigned long long>::max();
	if(n <= 1 || k == 1){
		return n;
	}
	if(k >= 64){
		return 1;
	}
	if(k == 2){
		return sqrtl(n);
	}

	if(n == LIM)n--;

	auto safe_mul = [&](unsigned long long &x, unsigned long long &y) -> void {
		if(x <= LIM / y){
			x *= y;
		}else{
			x = LIM;
		}
	};

	auto power = [&](unsigned long long a, int b) -> unsigned long long {
		unsigned long long ret = 1;
		while(b){
			if(b & 1)safe_mul(ret, a);
			safe_mul(a, a);
			b >>= 1;
		}
		return ret;
	};

	unsigned long long ret = (k == 3 ? cbrt(n)-1 : std::pow(n, std::nextafter(1.0/double(k), 0.0)));
	while(power(ret+1, k) <= n)ret++;
	return ret;
}

#line 2 "math/iroot.hpp"

#include<cmath>
#include<limits>

unsigned long long iroot(unsigned long long n, int k=2){
	constexpr unsigned long long LIM = std::numeric_limits<unsigned long long>::max();
	if(n <= 1 || k == 1){
		return n;
	}
	if(k >= 64){
		return 1;
	}
	if(k == 2){
		return sqrtl(n);
	}

	if(n == LIM)n--;

	auto safe_mul = [&](unsigned long long &x, unsigned long long &y) -> void {
		if(x <= LIM / y){
			x *= y;
		}else{
			x = LIM;
		}
	};

	auto power = [&](unsigned long long a, int b) -> unsigned long long {
		unsigned long long ret = 1;
		while(b){
			if(b & 1)safe_mul(ret, a);
			safe_mul(a, a);
			b >>= 1;
		}
		return ret;
	};

	unsigned long long ret = (k == 3 ? cbrt(n)-1 : std::pow(n, std::nextafter(1.0/double(k), 0.0)));
	while(power(ret+1, k) <= n)ret++;
	return ret;
}

Back to top page