C問題
方針
3重ループを行うと時間制限に間に合いません。
A,Bの範囲を絞った上で、条件を満たすCの個数を数え上げます。
■条件
A<=B<=C かつ A*B*C*==N
○Aの範囲
Aの最大値について、A*A*A==Nとなり、これ以上の数になるとＮよりも大きくなります。
そのためAの最大値はNの3乗根となります。
よって、Aの範囲は 1<=A<=Nの3乗根 です。
○Ｂの範囲
A<=B<=CよりＢの下限値は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を合計していけば解答となります。
解答
|
1 2 3 4 5 6 7 8 9 10 11 |
n = int(input()) ans = 0 for i in range(1,n+1): if i**3 > n : #iはA。Aの3乗がNを超えた場合は次のループへ進む break for j in range(i,n+1): #jはB。A*B*BがNを超えた場合は次のループへ進む if i*(j**2) > n: break ans += n//(i*j)-j+1 print(ans) |
コメント