$\lfloor N/i \rfloor$ の列挙 (src/NumberTheory/enumerate_quotients.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-11-25 18:44:26+09:00
Include: #include "src/NumberTheory/enumerate_quotients.hpp"

$\lbrack N\rbrack = \lbrace1,2,\dots,N\rbrace$ を $\left\lfloor \frac{N}{i} \right\rfloor$ が等しくなるような $i \in \lbrack N\rbrack$ でグループ分けをする.

返り値は $\lbrace(q_j,l_j,r_j): j=1,\dots,k\rbrace$ で表現しており, 各 $j$ について任意の $i\in ( l_j,r_j\rbrack$ で $\left\lfloor \frac{N}{i} \right\rfloor = q_j$ が成り立つ. $q_j$ が昇順になるように並べている.

関数	概要	計算量
`enumerate_quotients(N)`	上の通り	$O (\sqrt{N})$

Verified with

Code

#pragma once
#include <vector>
#include <algorithm>
#include <tuple>
#include <cmath>
#include <cstdint>
// (q,l,r) : i in (l,r], ⌊N/i⌋ = q
std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> enumerate_quotients(uint64_t N) {
 uint64_t sq= std::sqrt(N), prev= N, x;
 std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> ret;
 for (int q= 1, n= (sq * sq + sq <= N ? sq : sq - 1); q <= n; ++q) ret.emplace_back(q, x= double(N) / (q + 1), prev), prev= x;
 for (int l= sq; l >= 1; --l) ret.emplace_back(double(N) / l, l - 1, l);
 return ret;
}

#line 2 "src/NumberTheory/enumerate_quotients.hpp"
#include <vector>
#include <algorithm>
#include <tuple>
#include <cmath>
#include <cstdint>
// (q,l,r) : i in (l,r], ⌊N/i⌋ = q
std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> enumerate_quotients(uint64_t N) {
 uint64_t sq= std::sqrt(N), prev= N, x;
 std::vector<std::tuple<uint64_t, uint64_t, uint64_t>> ret;
 for (int q= 1, n= (sq * sq + sq <= N ? sq : sq - 1); q <= n; ++q) ret.emplace_back(q, x= double(N) / (q + 1), prev), prev= x;
 for (int l= sq; l >= 1; --l) ret.emplace_back(double(N) / l, l - 1, l);
 return ret;
}