十进制转三进制

题目描述

给定一个非负整数 $n$，请将其转换为三进制表示，并输出对应的三进制字符串。

什么是三进制？三进制是一种逢三进一的计数系统，每一位上的数字只能是 $0, 1, 2$ 之一。例如，三进制数 $(101)_3$ 表示：$1 \times 3^2 + 0 \times 3^1 + 1 \times 3^0 = 9 + 0 + 1 = 10$。所以十进制数 $10$ 的三进制表示为 101。

输入格式

输入一行，包含一个非负整数 $n$。

输出格式

输出一行，为 $n$ 的三进制表示。三进制字符串不应包含前导零，但数字 $0$ 本身应输出 0。

样例输入

样例输入 1

10

样例输入 2

0

样例输入 3

27

样例输出

样例输出 1

101

样例输出 2

0

样例输出 3

1000

样例解释

对于第一个样例，输入为 $10$。将 $10$ 转换为三进制时，可以不断除以 $3$ 并记录余数：

$10 \div 3 = 3$ 余 $1$

$3 \div 3 = 1$ 余 $0$

$1 \div 3 = 0$ 余 $1$

将余数倒序排列，得到 $101$。也可以验证：$1 \times 3^2 + 0 \times 3^1 + 1 \times 3^0 = 9 + 0 + 1 = 10$。因此输出为 101。

数据范围

• $0 \le n < 2^{31}$，即 $n$ 在 C/C++ 的 int 类型能表示的非负范围内。