cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AtCoder/abc230_e.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/abc230/tasks/abc230_e"

#include "../../Src/Template/TypeAlias.hpp"
#include "../../Src/Number/EnumerateQuotients.hpp"

#include <iostream>

using namespace zawa;

int main() {
    u64 N; std::cin >> N;
    EnumerateQuotients eq(N);
    u64 ans{};
    for (const auto& q : eq) {
        ans += q.len() * q.quotient();
    }
    std::cout << ans << std::endl;
}
#line 1 "Test/AtCoder/abc230_e.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc230/tasks/abc230_e"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Number/EnumerateQuotients.hpp"

#line 2 "Src/Number/IntegerDivision.hpp"

#include <type_traits>
#include <cassert>

namespace zawa {

template <class T>
constexpr T DivFloor(T a, T b) {
    static_assert(std::is_integral_v<T>, "DivFloor argument must be Integer");
    assert(b != T{});
    if constexpr (std::is_unsigned_v<T>) {
        return a / b;
    }
    else {
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        return (a >= 0 ? a / b : (a - b + 1) / b);
    }
}

template <class T>
constexpr T DivCeil(T a, T b) {
    static_assert(std::is_integral_v<T>, "DivCeil argument must be Integer");
    assert(b != T{});
    if constexpr (std::is_unsigned_v<T>) {
        return (a + b - 1) / b;
    }
    else {
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        return (a >= 0 ? (a + b - 1) / b : a / b);
    }
}

} // namespace zawa
#line 5 "Src/Number/EnumerateQuotients.hpp"

#line 7 "Src/Number/EnumerateQuotients.hpp"
#include <vector>
#include <utility>
#line 10 "Src/Number/EnumerateQuotients.hpp"

namespace zawa {

template <class Value>
class EnumerateQuotients {
public:
    class Data {
    private:
        Value quotient_;
        Value l_, r_;
    public:
        Data() = default;
        constexpr Data(Value quotient, Value l, Value r) : quotient_{ quotient }, l_{ l }, r_{ r } {
            assert(l < r);
        }
        
        constexpr Value quotient() const noexcept {
            return quotient_;
        }

        constexpr Value l() const noexcept {
            return l_;
        }

        constexpr Value r() const noexcept {
            return r_;
        }

        constexpr std::pair<Value, Value> range() const noexcept {
            return std::pair{ l_, r_ };
        }

        constexpr Value len() const noexcept {
            return r_ - l_;
        }
    };

private:
    std::vector<Data> seq_;
    Value n_;

    constexpr void templateTypeAssert() const noexcept {
        static_assert(std::is_integral_v<Value>, "Template argument must be unsigned integer type.");
        static_assert(std::is_unsigned_v<Value>, "Template argument must be unsigned integer type.");
    }

    constexpr void floorBuild() noexcept {
        Value l{1U};
        while (l <= n_) {
            Value quotient{ DivFloor(n_, l) };
            Value r{ DivFloor(n_, quotient) + 1 };
            seq_.emplace_back(quotient, l, r);
            l = r;
        } 
    }

    constexpr void ceilBuild() noexcept {
        Value l{1U};
        while (l < n_) {
            Value quotient{ DivCeil(n_, l) };
            Value r{ DivCeil(n_, quotient - 1) };
            seq_.emplace_back(quotient, l, r);
            l = r;
        }
        if (n_) {
            seq_.emplace_back(1U, n_, n_ + 1);
        }
    }

public:
    constexpr EnumerateQuotients() : seq_{}, n_{} {
        templateTypeAssert();
    }

    constexpr EnumerateQuotients(Value n, bool floor = true) : seq_{}, n_{ n } {
        templateTypeAssert();
        floor ? floorBuild() : ceilBuild();
        seq_.shrink_to_fit();
    }

    constexpr Value n() const noexcept {
        return n_;
    }

    constexpr Data operator[](u32 i) const noexcept {
        return seq_[i];
    }

    constexpr Value quotient(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].quotient();
    }

    constexpr Value l(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].l();
    }

    constexpr Value r(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].r();
    }

    constexpr std::pair<Value, Value> range(u32 i) const noexcept {
        assert(i < seq_.size());
        return std::move(seq_[i].range());
    }

    constexpr Value len(u32 i) const noexcept {
        assert(i < seq_.size());
        return seq_[i].len();
    }

    constexpr usize size() const noexcept {
        return seq_.size();
    }

    constexpr typename decltype(seq_)::const_iterator begin() const noexcept {
        return seq_.begin();
    }

    constexpr typename decltype(seq_)::const_iterator end() const noexcept {
        return seq_.end();
    }

};

} // namespace zawa
#line 5 "Test/AtCoder/abc230_e.test.cpp"

#include <iostream>

using namespace zawa;

int main() {
    u64 N; std::cin >> N;
    EnumerateQuotients eq(N);
    u64 ans{};
    for (const auto& q : eq) {
        ans += q.len() * q.quotient();
    }
    std::cout << ans << std::endl;
}
Back to top page