power sum （累乗和）
(utilities/pow_sum.hpp)

• View this file on GitHub
• Last update: 2026-04-11 15:33:38+09:00
• Include: #include "utilities/pow_sum.hpp"

繰り返し二乗法で $(x^n, \sum_{i=0}^{n-1} x^i)$ の組を計算．計算量は $O(\log n)$．

問題例

• AtCoder Beginner Contest 212 H - Nim Counting

Verified with

• utilities/test/pow.test.cpp

Code

#pragma once
#include <bit>
#include <type_traits>
#include <utility>

// {x^n, x^0 + ... + x^(n - 1)} for n >= 0
// Verify: ABC212H
template <typename T, typename Int> std::pair<T, T> pow_sum(T x, Int n) {
    using Uint = std::make_unsigned_t<Int>;
    if (n == 0) return {1, 0};
    T sum = 1, p = x; // ans = x^0 + ... + x^(len - 1), p = x^len
    for (int d = std::bit_width(Uint(n)) - 2; d >= 0; d--) {
        sum = sum * (p + 1);
        p *= p;
        if ((n >> d) & 1) {
            sum += p;
            p *= x;
        }
    }
    return {p, sum};
}

#line 2 "utilities/pow_sum.hpp"
#include <bit>
#include <type_traits>
#include <utility>

// {x^n, x^0 + ... + x^(n - 1)} for n >= 0
// Verify: ABC212H
template <typename T, typename Int> std::pair<T, T> pow_sum(T x, Int n) {
    using Uint = std::make_unsigned_t<Int>;
    if (n == 0) return {1, 0};
    T sum = 1, p = x; // ans = x^0 + ... + x^(len - 1), p = x^len
    for (int d = std::bit_width(Uint(n)) - 2; d >= 0; d--) {
        sum = sum * (p + 1);
        p *= p;
        if ((n >> d) & 1) {
            sum += p;
            p *= x;
        }
    }
    return {p, sum};
}

Back to top page