ABC156 B - Digits

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = map(int, sys.stdin.readline().split())

    ret = 0
    while N > 0:
        N = N // K
        print(N)
        ret += 1

    print(ret)


if __name__ == '__main__':
    main()

考え方

位取り記数法により、
整数NをKで割った値をNに置き換えて、Kで割ることが出来る回数が桁数。（らしい）
下記の記事を読んで、雰囲気だけ理解した。

位取り記数法 | 日経クロステック ラーニング

位取り記数法の計算法と応用問題(シリーズ第2回)

10進法では整数が1, 2, 3, ... 8, 9, 10, 11と順に数が増え、
9から10になるタイミングで一桁増える。
つまり10進法では1つの桁数を0 ~ 9の10個の数値で表現している。
そのため、10進法では整数を10で割ることが出来る回数 = 桁数。

2進法、8進法、16進法も同様の考えをすることができる。
例えばNが11、Kが2のとき、
整数11を2進法で表すと1011になる。
2進法では1, 10, 11, 100, 101, ... , 1011, 1100, 1101と数が増える。
2進法も0と1の2つの数値で桁数を表現しているため、
整数NをKで割った値をNに置き換えて、Kで割ることが出来る回数が桁数となる。