第3题

using i64 = long long;

i64 solve1(i64 n)
{
    std::vector<i64> c(n);
    c[0] = 0;
    i64 sum = 0;
    for (i64 i = 1; i < n; ++i)
    {
        c[i] = c[i / 2] + (i % 2);
        sum += c[i];
    }
    return sum;
}

std::pair<i64,i64> solve2(i64 n)
{
    if (n == 0)
        return {0, 0};
    auto r = n % 2;
    auto q = n / 2;
    auto [s, c] = solve2(q);
    if (r == 1)
        return {s*2 + q + c, c + 1};
    else
        return {s*2 + q, c};
}

若输入参数 $n$ 在0到1024之间，则 solve1(n) 的返回值与 solve2(n) 的第一项返回值必定相等（ ）。

{{ select(1) }}

• 正确
• 错误