【Python】Atcoder Beginner Contest 227 C問題 解答・解説

この記事は約2分で読めます。

 

C問題

方針

3重ループを行うと時間制限に間に合いません。

A,Bの範囲を絞った上で、条件を満たすCの個数を数え上げます。

■条件

A<=B<=C かつ A*B*C*==N

○Aの範囲

Aの最大値について、A*A*A==Nとなり、これ以上の数になるとNよりも大きくなります。

そのためAの最大値はNの3乗根となります。

よって、Aの範囲は 1<=A<=Nの3乗根 です。

○Bの範囲

A<=B<=CよりBの下限値はAです。

Bの上限値はA*B*C==Nより、B*C==N/A

B==Cの時がBの最大値となるので、B*B==N/A

→ B==N/(A*B)が最大値です。(Cも同様)

Bの範囲は A<=B<=N/(A*B)

○条件を満たすCの範囲

Cの下限値は、A<=B<=CよりBとなります。

Cの最大値はBと同じくN/(A*B)です。

A<=B<=C かつ A*B*C*==Nを満たすのは、

よって、Cの範囲はB<=C==N/(A*B)となります。

C<= N/(A*B) – B +1

※Cの最大値であるN/(A*B) から、Cの下限値であるBを引きます。

また、Cの範囲はBそのものの値も含まれているので1を加えています。

C<= N/(A*B) – B +1を合計していけば解答となります。

 

解答

 

コメント