[ARC164] A - Ternary Decomposition

[Q] https://atcoder.jp/contests/arc164/tasks/arc164_a

考察
・Nをできるだけ大きい数で分解する。
・3^39 = 4,052,555,153,018,976,267 > 1e18
なので、3^39から3^0まで分解して、最小の分解数Xを求める。
・分解した要素について。
3 = 1 + 1 + 1と分解すれば、分解数を2つ増やせる。任意に2ずつ増やせる。
・KがX+2の倍数で表せるならYes。

N = 26を考える。

N = 9 + 9 + 3 + 3 + 1 + 1
の6要素に分けられる。

これは、9 = 3 + 3 + 3にすれば、
N = 9 + (3 + 3 + 3) + 3 + 3 + 1 + 1
の8要素に分けられる。

ほかにも、3 = (1 + 1 + 1)にすれば、
N = 9 + (3 + 3 + 3) + 3 + (1 + 1 + 1) + 1 + 1
の10要素に分けられる。

最も少ない分解数がわかったら、+2ずつバリエーションをもたせられることがわかった。

実装

int main() {
  cincout();

  ll T;
  cin >> T;
  ll pow3[100]{};
  pow3[0] = 1;
  rep(i, 39) { pow3[i + 1] = pow3[i] * 3; }
  while (T--) {
    ll N, K;
    cin >> N >> K;

    ll cnt = 0; // 最小の分解要素数
    ll n = N;
    ll dis = 39;
    while (n > 0) {
      while (pow3[dis] > n) --dis;
      cnt += n / pow3[dis];
      n %= pow3[dis];
    }
    if (cnt <= K && ((K - cnt) % 2 == 0)) { 分解要素数に、任意に2を足したときにKになるか
      cout << "Yes" << endl;
    } else
      cout << "No" << endl;
  }
}

https://atcoder.jp/contests/arc164/submissions/43419646