【ABC180 C】「Cream puff」を解く【Python3】

コンテスト一覧へ

 

N個のシュークリームを平等に分けることができるような人数として、あり得るものをすべて求める問題です。

提出
import math

n = int(input())
ans = []

for i in range(1,math.floor(math.sqrt(n))+1):
    if n%i == 0:
        ans.append(i)
        ans.append(n//i)

l = sorted(set(ans))

for i in l:
    print(i)

平等に分けることができる人数iは、N÷i が0となるようなものです。

空リスト「ans」を作成しておきます。

for文を用いて、1から順番に確かめていき、「n%i == 0」であれば、「ans」に加えていきます。

ただ、Nの最大値が「1012」であるため、Nまでの数字すべてを調べていては、時間が間に合いません。

iとともに「n/i」を加えることで計算量を減らすことができます。

i2がNを超えるところまで調べればいいので、for文の2つ目の引数を「√N+1」にします。

√Nが整数の場合(N=16など)は、ansに重複した数値が加わるため、set()で重複を削除し、ソートします。

ansを順番に出力したものが答えになります。

スポンサーリンク

【ABC180】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。