【白俊】1188号:食べ物評論家の解答

質問する
善英の職業はソーセージ料理人です.ソーセージを売る前に、M人の食べ物評論家を集めて味をテストしたいと思っています.
善英は同じソーセージをN個用意した.このソーセージはすべての評論家が等量に切りたいと思っている.このとき、ソーセージを切る回数を最小限に抑えたいと思います.
例えば、ソーセージが2つ、評論家が6人いると仮定します.このとき、ソーセージを3つにして、評論家ごとに1つあげればいいです.この場合、ソーセージは全部で4回切ります.他にもソーセージが3つと評論家が4人いる場合を考えてみましょう.このとき、ソーセージ1本あたりの大きさを3:1に切り、評論家に大きな塊を渡し、残りの破片を評論家に渡すと、同じ量が得られます.
ソーセージの数と評論家の数を指定する場合は、すべての評論家に必要なナイフの数を求めて、同じ数のソーセージを与えるプログラムを作成してください.
入力
最初の行はソーセージの数Nと評論家の数Mを与えた.(1 ≤ N, M ≤ 100)
しゅつりょく
最初の行ですべての評論家に同数のナイフ法を出力する回数の最高値.
に答える
ソーセージをN個つなぎます.M人の評論家はN/M個のソーセージをそれぞれ分かち合う.このとき、ソーセージを切る必要はありません.
すなわち,NがMに分割されると,カットする必要はなく,NとMの最大公約数を見出す.
最悪の場合(最大公約数が1の場合)はM-1をカットし、NをMで割った数がMに等しい場合はM-(NとMの最大公約数)、すなわち0回カットします.
完全なコード

N, M = map(int, input().split())

# a와 b의 최대 공약수
def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)

# 최악의 경우 M-1번 잘라야 함
print(M - gcd(N, M))

大学で暗号学の授業を受けたとき、gcdを習ったのを覚えています.最大公約数が考えられるので思ったより早いです.