算法
(二进制数) $O(\log N)$
我们可以考虑倒过来推,可以对 $N$ 执行以下操作,直到 $N$ 变成 $0$ 为止:
- 若 $N$ 为偶数,则将它除以 $2$,若 $N$ 为奇数,则将它减一
比如 $N = 5$ 时,
我们可以有
$$ {\color{Blue} {5 \stackrel{-1}{\longrightarrow} 4 \stackrel{\div 2}{\longrightarrow} 2 \stackrel{\div 2}{\longrightarrow} 1 \stackrel{-1}{\longrightarrow} 0}} $$
换个角度考虑, $5$ 也是二进制数 101
于是,我们可以得到
$$ {\color{Blue} {101 \stackrel{-1}{\longrightarrow} 100 \stackrel{\div 2}{\longrightarrow} 10 \stackrel{\div 2}{\longrightarrow} 1 \stackrel{-1}{\longrightarrow} 0}} $$
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::string;
using ll = long long;
int main() {
ll n;
cin >> n;
string ans;
while (n) {
if (n & 1) {
ans += 'A';
n ^= 1;
}
else {
ans += 'B';
n >>= 1;
}
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
return 0;
}