T778646 模拟赛1 T2 拆分数字（split）

题目描述

小明同学探索到一个古老的数学遗迹，在遗迹的深处发现了若干到道神秘的谜题。谜题中给出了整数 \(n\) 和 \(k\) ，并有如下提示：“在这个神秘的地方，存在着一类特殊的数字，它们的形式为 \(3^m\)（\(m\) 是非负整数）。现在需要判断能否通过恰好 \(k\) 个这样的特殊数字相加，得到整数 \(n\) 。

换言之，是否存在一个非负整数序列 \(\{a_k\}\)，使得 \(n = 3^{a_1} + 3^{a_2} + ... + 3^{a_k}\)。

不出意外的，小明同学又把这个任务交给你了。

输入格式

输入的第一行包含一个正整数 \(T\)，表示谜题的个数。

接下来 \(T\) 行，每行两个整数 \(n,k\)，表示一道谜题中的信息。

输出格式

输出共 \(T\) 行。对于每一道谜题，如果可以则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

4
5 3
17 2
163 79
1000000000000000000 1000000000000000000

输出 #1

Yes
No
Yes
Yes

输入输出样例 #2

输入 #2

10
651 1
313 2
415 2
704 1
476 1
997 2
472077225 323578330
952398106 685604628
633466414 519840096
989009073 752053728

输出 #2

No
No
No
No
No
No
No
Yes
Yes
No

说明/提示

样例 1 解释

对于第一个测试案例，\(5 = 3^1 + 3^0 + 3^0\)，因此满足了相关条件。

对于第二个测试案例，没有非负整数序列 \(a_1,a_2\) 使得 \(17 = 3^{a_1} + 3^{a_2}\)，因此不满足有关条件。

数据规模与约定

• 对于 \(30\%\) 的数据，保证 \(n \le 10, k \le 5\)。
• 对于另 \(30\%\) 的数据，保证 \(n \le 1000,k \le 2\)。
• 对于 \(100\%\) 的数据，保证 \(1 \le k \le n \le 1 \times 10^{18},1\le T\le1 \times 10^5\)。

这题其实就考了个进制转换

\(n=s^A1+s^A2+...+s^An\)
这个形式意思是：
\((n)_{10}=(A1A2...An)_s\)
而题目中无非就是令s=3而已
思路和代码放上来了

ACcode：

#include
using namespace std;
const int N=1;
int t;
/*
3进制
假设每一位时a[i]
意思是n在这一位上有a[i]个 3的i次方
所以min=d[1]+d[2]+...+d[i]
而一个3的i次方可以拆成3*(3的(i-1)次方)
所以个数会加2g，g是非负整数
条件：
1.min<=k<=n (k=n是合法的)
2.(k-min)是偶数，因为逐2相加
*/
int main(){
	//超时！？
	scanf("%d",&t);
	while(t--){
		unsigned long long n,k,sum=0,csp;
		scanf("%lld %lld",&n,&k);
		csp=n;
		while(csp>0){ //求3进制时n的各个位数之和(min)
			int x=csp%3;
			sum+=x;
			csp/=3;
		}
		if(sum<=k and k<=n and (k-sum)%2==0) cout<<"Yes"<