ARC164题解

• A：数学，进制
• B：图论
• C：博弈论

Tasks - AtCoder Regular Contest 164

A - Ternary Decomposition

**题目描述：**给定一个数N，请问能否恰好使用K个 $3^{m}$ (m>=0)的形式的数相加来表示

收获：

• 看到$2^{m}，3^{m}$ 这种联想到进制表示，即将十进制转化为3进制表示

• N用三进制表示的数每个位上数字累加之和S，含义为N至少要由S个$3^{m}$ 形

  式来表示

例如:$5=12_{(3)}=3^{1}+2*3^{0}$,而S=1+2=3。所以5至少需要3个这样数字才能表示。

而$3^{1}=3*3^{0}$，每有一个$3^{1}$变为3个$3^{0}$可以增加两个数
类似递推，高次方都可以多贡献偶数个个数出来

• 结论：N可由{S，S+2,S+4…S+2n(S+2n==N)} 个数字来表示，即大于等于S且和N同奇偶性的个数。