Ternary Decomposition

题意

共 \(T\) 组数据，对于每组数据，给出两个整数 \(n\) 和 \(k\)，问是否存在一个长度为 \(k\) 的非负整数序列 \(a\)，使得 \(\sum\limits_{1 \leqslant i \leqslant k} 3^{a_i} = n\)，若存在，输出 Yes，否则输出 No。

数据范围

\(1 \leqslant T \leqslant 10^5\)。
\(1 \leqslant k \leqslant n \leqslant 10^{18}\)。

思路

整体思路类似 CF1095C，把 \(n\) 转为三进制。

首先判断一下，\(n\) 最多只能分为 \(n\) 个 \(1\) 相加，若 \(n < k\)，则必然不成立(虽然题目保证了 \(n \geqslant k\))。

令 \(n = (\overline{x_1x_2x_3\cdots x_m})_3\)，则 \(a\) 的长度(设为 \(t\))至少为 \(\sum\limits_{1\leqslant i \leqslant m} x_i\)，当 \(t > k\) 时，很明显也不成立，当 \(t = k\) 时成立，那么当 \(t < k\) 时呢？

若消除一个 \(x^i (i > 0)\)，则需要用 \(3\) 个 \(x^{i-1}\) 来替代，会使 \(t\) 加 \(2\)，那么剩下一种情况就推出来了，当 \(k - t\) 为偶数时，成立。

整理一下

当 \(n < k\) 时，不成立。
当 \(n \geqslant k\) 时，令 \(n = (\overline{x_1x_2x_3\cdots x_m})_3\)，\(t = \sum\limits_{1\leqslant i \leqslant m} x_i\)；
- 当 \(t > k\) 时，不成立。
- 当 \(t=k\) 时，成立。
- 当 \(t < k\) 时，若 \(t\equiv k\pmod{2}\)，则成立；否则不成立。

Code

#include <bits/stdc++.h>

using namespace std;

int t;
long long n, k, s;

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> t; t; t--, s = 0) {
    cin >> n >> k;
    /* if (k > n) { 题目已经保证 n >= k 了，不必要。
      cout << "No\n";
      continue;
    } */
    while (n) { // 三进制分解
      s += n % 3, n /= 3;
    }
    cout << (s <= k && s % 2 == k % 2 ? "Yes" : "No") << '\n'; // 各情况分析见上
  }
  return 0;
}