Atcoder 216 C問題[Many balls] についての質問

Question

Atcoder 216 C問題[Many balls] についての質問です。(計算量について?)

問題文

"空の箱があります。
髙橋君は以下の 2 種類の魔法を好きな順番で好きな回数使えます。
魔法 A ：箱の中にボールを 1 つ増やす
魔法 B ：箱の中のボールの数を 2 倍にする
合計 120 回以内の魔法で、箱の中のボールの数をちょうど N 個にする方法を 1 つ教えてください。
なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。
魔法以外の方法でボールの数を変化させることはできません。"
https://atcoder.jp/contests/abc216/tasks/abc216_c

という具合に 特定の値にA→ 数に+1 B→数を２倍 という2つの操作を通じて到達させよ、という問題なのですが、不明な点があります。

自分で考えたコードで①は通らず、回答例のコード②で通るのは何故でしょうか...?
相違点としては、いったん与えられた値をremに代入しているかどうかだと思うのですが、なぜそれで違いがでるのかが分かりません。
どなたかご教授いただけますと幸いです。

①自分で考えたコード

def main():
  n = int(input())
  ans = ""

  while n>0:
    if n%2 == 0:
      n = n/2
      ans += "B"
    else:
      n = n-1
      ans += "A"  
  print(command[::-1])  


if __name__ == '__main__':
  main()

②回答例のコード
(https://qiita.com/u2dayo/items/dd17bab5d443bf7a1a67#c%E5%95%8F%E9%A1%8Cmany-balls より)

def main():
  N = int(input())
  ans = ""
  rem = N

  while rem:
    if rem % 2 == 1:
      ans += "A"
      rem -= 1
    else:
      ans += "B"
      rem //= 2
  print(ans[::-1])

if __name__ == '__main__':
    main()

Answer 1

Python3で割り算に/を使うと、結果はfloatになります。
そして、floatの有効桁は16桁弱です。
しかし、この問題の入力の最大は10^18なので、floatで表現できる範囲を超えています。

実際、以下のような入力に対して、(2^54+2)

18014398509481986

正しい結果は以下ですが、

ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBAB

ご呈示のコードですと以下になります。(末尾近くのAが無い)

ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

Comments

[guppi65513461]

なるほど！
有効桁の都合で正しく計算できなくなるのですね..勉強になりました
ありがとうございます！