AtCoder Beginner Contest 112 D – Partition をPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
AtCoder Beginner Contest 112 D – Partition

軽い考察さえできれば、約数列挙をすれば解けることに気づける……はず？

# AtCoder Beginner Contest 112 D - Partition
# https://atcoder.jp/contests/abc112/tasks/abc112_d
# tag: 整数 最大公約数 約数列挙 典型問題

# M は求める最大公約数で割り切れる必要がある。
# そこで、M のある約数を d とすると、
# 作成される数列は、全て d で割り切れる必要がある。
# よって、数列の合計は d * N 以上でなければならない。
# つまり、M >= d * N を満たす最大の d が答えとなる。

def main():
    N, M = map(int, input().split())

    # 約数列挙。この問題で重複を避ける意味はないが、まあ一応。
    divisors = []
    for d in range(1, int(M**0.5) + 1):
        if M % d == 0:
            divisors.append(d)
            if d * d != M:
                divisors.append(M // d)

    # 昇順にソートしておく
    divisors.sort()

    result = 1

    # 小さいものから順に、条件を満たすかどうかを確認
    for d in divisors:
        if M >= d * N:
            result = d
        # 条件を満たさなくなれば打ち切る
        else:
            break

    print(result)

main()

abc112_d.py view raw

関連

コメントを残すコメントをキャンセル