魔法 \(A\) で追加されるボールの色は毎回異なるとします。
また、魔法 \(B\) では色が保存されたままボールが複製されるとします。

さて、\(S\) の \(i\) 文字目が A で、このとき青いボールを追加したとしましょう。
\(S\) の \(i+1\) 文字目以降に含まれる B の数を \(k\) 個とすると、最終的に青いボールは \(2^k\) 個になります。

よって、\(N=2^p+2^q+2^r+\cdots\) と分解すれば、それに基づいて(長さが \(120\) 以下とは限らないものの) \(S\) を構築できます。

したがって、以下のようにすることで構築が可能です。

\(ans\) を、 B を \(60\) 個繋げた文字列とする。
\(N\) の二進表記を \(A\) とする。

\(A\) の上の桁から順番に見ていき、以下の操作を行う。

• \(2^k\) の桁が 1 ならば、\(ans\) の、後ろに B が \(k\) 個ある場所に A を挿入する

\(10^{18} \lt 2^{60}\) なので、\(A\) の桁数は \(60\) 以下です。
したがって \(ans\) の長さは \(120\) 以下で、条件を満たします。

C++での実装例：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main(){
    ll n;cin>>n;
    const ll len=60;
    auto a=bitset<len>(n);
    string ans(len,'B');
    for(ll i=len-1;i>=0;i--){
        if(a[i]==1){
            ans.insert(ans.size()-i,"A");
        }
    }
    cout<<ans<<endl;
    return 0;
}