题解

需要判断 $n$ 是否能表示为恰好 $k$ 个数之和，其中每个数都是 $1,3,9,\ldots$ 中的一个，且同一个数可以重复使用．换句话说，我们只关心一个整数能否表示成指定项数的 $3$ 的幂之和．

算法 0：按总人数和队伍数动态规划

当 $n$ 很小时，令 $f_{s,c}$ 表示是否能用恰好 $c$ 个三次幂凑出总和 $s$．从 $f_{0,0}=1$ 出发，枚举要加入的三次幂并转移到 $f_{s+3^x,c+1}$．

若直接实现，单组询问的时间复杂度为 $O(nk\log n)$，空间复杂度为 $O(nk)$．

预期通过 subtask 1、2，预期得分为 $25$ 分．

算法 1：特殊性质

当 $k\le2$ 时：若 $k=1$，直接判断 $n$ 是否为 $3$ 的幂；若 $k=2$，枚举第一项 $3^x$，再判断 $n-3^x$ 是否为 $3$ 的幂．朴素实现的时间复杂度为 $O(\log^2 n)$，也可以预处理所有不超过 $10^{18}$ 的 $3$ 的幂后用集合查询做到 $O(\log n)$．预期通过 subtask 3，预期得分为 $15$ 分．

当 $n=3^x$ 时，最初可以只有一个大小为 $3^x$ 的小队．把一个大小为 $3^y$ 的小队拆成三个大小为 $3^{y-1}$ 的小队，会使小队数量增加 $2$．因此恰好可以得到所有不超过 $n$ 的奇数队伍数．预期通过 subtask 4，预期得分为 $20$ 分．

算法 2：三进制数位和

把 $n$ 写成标准三进制形式：

令

为三进制数位和．标准三进制展开本身给出了一个使用 $s$ 个三次幂的方案．

如果某个表示中同一位出现至少三个 $3^x$，就可以把它们合并成一个 $3^{x+1}$，项数减少 $2$．持续合并最终必然得到唯一的标准三进制展开，所以任何表示使用的项数都不小于 $s$，并且与 $s$ 奇偶性相同．

另一方面，从标准展开开始，只要当前方案中还存在一个大于 $1$ 的项，就可以将一个 $3^x$ 拆成三个 $3^{x-1}$．每次拆分使项数恰好增加 $2$；持续拆分最终会得到 $n$ 个 $1$．因此拆分过程依次取得 $s,s+2,\ldots,n$ 中的每一个项数，不会跳过任何与 $s$ 同奇偶的候选值．

因此答案为 Yes 当且仅当

正确性证明

上述合并说明，所有合法表示的项数必须至少为 $s$，且与 $s$ 同奇偶；显然项数也不会超过全为 $1$ 时的 $n$．因此条件是必要的．上述逐次拆分构造会取得区间 $[s,n]$ 内所有与 $s$ 同奇偶的项数，因此条件也是充分的．算法按照这个充要条件判断，故答案正确．

每组询问只需枚举 $n$ 的三进制数位，时间复杂度为 $O(\log_3 n)$，空间复杂度为 $O(1)$．全部询问的时间复杂度为 $O(T\log n)$．实现时直接反复对 $n$ 除以 $3$，不需要显式生成更大的 $3$ 的幂，因此使用有符号 $64$ 位整数即可安全处理 $n\le10^{18}$．

预期通过所有 subtask，预期得分为 $100$ 分．

参考代码

#include <cstdint>
#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int test_cases;
    std::cin >> test_cases;
    while (test_cases--) {
        std::int64_t n, k;
        std::cin >> n >> k;
        std::int64_t digit_sum = 0;
        for (std::int64_t x = n; x > 0; x /= 3) {
            digit_sum += x % 3;
        }
        bool possible = digit_sum <= k && k <= n && ((k - digit_sum) % 2 == 0);
        std::cout << (possible ? "Yes" : "No") << '\n';
    }
    return 0;
}