← 返回题目列表

AtCoder · arc164_a

A. 三元分解

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你整数 N 和 K。 是否可以表达 N 正好是 K 表格的编号 3^m (m 是一个非负整数)? 换句话说,是否存在非负整数序列 (m_1, m_2,\ldots, m_K) 这样:

N= 3^{m_1}+3^{m_2}+...+3^{m_K}?

你被给予 T 测试用例。逐一回答。

约束

  • 1 \leq T \leq 10^5
  • 1 \leq K \leq N \leq 10^{18}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots 
\mathrm{case}_T

每个测试用例, \mathrm{case}_i (1\leq i \leq T)的格式如下:

N K

输出

打印 T 行。的 i- 第行应包含 Yes 如果存在寻找的非负整数序列 i- 第一个测试用例,以及 No 否则。


示例输入 1

4
5 3
17 2
163 79
1000000000000000000 1000000000000000000

示例输出 1

Yes
No
Yes
Yes

对于第一个测试用例,我们有 5=3^1+3^0+3^0,因此满足所讨论的条件。

对于第二个测试用例,没有非负整数序列 (m_1, m_2) 这样 17=3^{m_1}+3^{m_2},因此不满足所讨论的条件。