Namaran

Code daily. Without assist.

2026-10-12

tower.cpp

#include <cstdint>

template <class... T>
constexpr std::uint64_t tower(T... xs) {
}

引数を数学の累乗の塔のように右から結合した値を返す tower を書いてください。tower(a, b, c) なら、a の (b の c 乗) 乗です。引数は1個以上の非負の整数で、1個ならその値を返し、0 の 0 乗は 1 とします。結果が std::uint64_t に収まる入力だけを考えればよく、static_assert の中のようにコンパイル時にも呼べるようにします。

入力例 1

tower(2, 3, 2)

出力例 1

512

入力例 2

tower(2, 2, 2, 2)

出力例 2

65536

入力例 3

tower(7)

出力例 3

7
Reference
#include <cstdint>

struct Pow {
    std::uint64_t v;
};

constexpr Pow operator^(Pow base, Pow exp) {
    std::uint64_t r = 1;
    for (std::uint64_t i = 0; i < exp.v; i++)
        r *= base.v;
    return {r};
}

template <class... T>
constexpr std::uint64_t tower(T... xs) {
    return (Pow{static_cast<std::uint64_t>(xs)} ^ ...).v;
}

累乗の塔は右から結合するので、計算は最後の2つの引数から始まります。tower(2, 3, 2) は 3 の 2 乗の 9 を先に求め、2 の 9 乗で 512 になります。C++ には累乗の演算子がなく、^ は排他的論理和です。そこで累乗を ^ に受け持たせた型 Pow を用意し、引数をすべて Pow に包んで、畳み込み式で ^ をつなぎます。

演算子を多重定義しても、優先順位と結合性は組み込みの ^ のまま変わりません。Pow 同士を a ^ b ^ c と並べれば左結合で (a ^ b) ^ c になります。結合の向きを決めるのは畳み込み式の形のほうです。(E ^ ...) は単項の右畳み込みで、E1 ^ (E2 ^ (... ^ En)) と右側に括弧を付けて展開されます。(... ^ E) と書くと左畳み込みになり、tower(2, 3, 2) は 2 の 3 乗の 2 乗、64 になってしまいます。引数が1個なら、単項の畳み込みはその要素そのものです。

operator^ は指数の回数だけ掛け算を繰り返します。指数が 0 ならループは1回も回らずに 1 を返すので、0 の 0 乗も 1 です。std::pow は浮動小数点数で計算するので、2 の 53 乗を超える結果では下の桁が正確に出ないことがあります。

掲載したのは参考実装で、唯一の正解ではありません。引数を std::uint64_t の配列に展開し、末尾から先頭へ向かって累乗を重ねるループでも書けます。