Score : $300$ points

问题描述

我们有一个空盒子。
高桥可以任意顺序、任意次数地施放以下两种法术。

• 法术 $A$: 向盒子里放入一个新球。
• 法术 $B$: 将盒子里球的数量翻倍。

请告诉我们一种方法，使用 最多 $\mathbf{120}$ 次 法术施放，使得盒子里恰好有 $N$ 个球。
在给定的约束条件下，可以证明总是存在这样的方法。

除了法术之外，没有其他方式改变盒子里球的数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell $A$: puts one new ball into the box.
• Spell $B$: doubles the number of balls in the box.

Tell us a way to have exactly $N$ balls in the box with at most $\mathbf{120}$ casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

• $1 \leq N \leq 10^{18}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

Output

Print a string $S$ consisting of A and B. The $i$-th character of $S$ should represent the spell for the $i$-th cast.

$S$ must have at most $\mathbf{120}$ characters.

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: $0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5$.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: $0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14$.
It is not required to minimize the length of $S$.

update @ 2024/3/10 09:34:46