Quotients of integer （商列挙）
(utilities/quotients.hpp)

• View this file on GitHub
• Last update: 2023-12-26 22:24:23+09:00
• Include: #include "utilities/quotients.hpp"

正の整数 $n$ に対して $\lfloor n / k \rfloor$ （ $k$ は整数）の形で表される整数を昇順に列挙する．計算量は $O(\sqrt{n})$.

使用方法

long long n = 10;
vector<long long> v = get_quotients(n);  // 1, 2, 3, 5, 10

問題例

• Library Checker: Enumerate Quotients

Verified with

• utilities/test/quotients.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>

// Generate all quotients of n
// return: n/1, n/2, ..., n
// Complexity: O(sqrt(n))
template <class T = long long> std::vector<T> get_quotients(T n) {
    std::vector<T> res;
    for (T x = 1;; ++x) {
        if (x * x >= n) {
            const int sz = res.size();
            if (x * x == n) res.push_back(x);
            res.reserve(res.size() + sz);
            for (int i = sz - 1; i >= 0; --i) {
                T tmp = n / res.at(i);
                if (tmp < x) continue;
                if (tmp == x and tmp * tmp == n) continue;
                res.push_back(tmp);
            }
            return res;
        } else {
            res.push_back(x);
        }
    }
}

#line 2 "utilities/quotients.hpp"
#include <algorithm>
#include <vector>

// Generate all quotients of n
// return: n/1, n/2, ..., n
// Complexity: O(sqrt(n))
template <class T = long long> std::vector<T> get_quotients(T n) {
    std::vector<T> res;
    for (T x = 1;; ++x) {
        if (x * x >= n) {
            const int sz = res.size();
            if (x * x == n) res.push_back(x);
            res.reserve(res.size() + sz);
            for (int i = sz - 1; i >= 0; --i) {
                T tmp = n / res.at(i);
                if (tmp < x) continue;
                if (tmp == x and tmp * tmp == n) continue;
                res.push_back(tmp);
            }
            return res;
        } else {
            res.push_back(x);
        }
    }
}

Back to top page