/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 N,K が与えられます。 N を、3^m （m は非負整数）の形の数をちょうど K 個用いた和として表すことは可能でしょうか。 すなわち、
N= 3^{m_1}+3^{m_2}+...+3^{m_K}
となるような非負整数の列 (m_1, m_2,\ldots , 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 行目には、i 番目のテストケースについて、題意の非負整数の列が存在する場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
4 5 3 17 2 163 79 1000000000000000000 1000000000000000000
出力例 1
Yes No Yes Yes
1 つめのテストケースについて、 5=3^1+3^0+3^0 と表すことができるため、題意の条件を満たしています。
2 つめのテストケースについて、17=3^{m_1}+3^{m_2} となる非負整数の列 (m_1, m_2) は存在しないため、題意の条件を満たしていません。
Score : 300 points
Problem Statement
You are given integers N and K. Is it possible to express N as the sum of exactly K numbers of the form 3^m (m is a non-negative integer)? In other words, is there a sequence of non-negative integers (m_1, m_2,\ldots, m_K) such that:
N= 3^{m_1}+3^{m_2}+...+3^{m_K}?
You are given T test cases. Answer each of them.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq K \leq N \leq 10^{18}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case, \mathrm{case}_i (1\leq i \leq T), is in the following format:
N K
Output
Print T lines. The i-th line should contain Yes if there is a sought sequence of non-negative integers for the i-th test case, and No otherwise.
Sample Input 1
4 5 3 17 2 163 79 1000000000000000000 1000000000000000000
Sample Output 1
Yes No Yes Yes
For the first test case, we have 5=3^1+3^0+3^0, so the condition in question is satisfied.
For the second test case, there is no sequence of non-negative integers (m_1, m_2) such that 17=3^{m_1}+3^{m_2}, so the condition in question is not satisfied.