shin3110
@shin3110

Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

n > 0 と n != 0 が違うだけでACかTLEが変わる原因

n > 0 と n != 0 の違い(速さなど)が知りたいです

AtCoderのABC280, D問題についてなのですが、以下のコードがなぜTLEになるのかを教えて下さい。

TLEになるコード

from collections import defaultdict

k = int(input())
cnt = defaultdict(int)

s = k
i = 2
while i*i <= k and s != 1:
    while s%i == 0:
        cnt[i] += 1
        s //= i
    i += 1

if s != 1:
    cnt[s] += 1

ans = 1
for a, b in cnt.items():
    j = 1
    while b != 0:
        n = a * j
        while n%a == 0:
            n //= a
            b -= 1
        j += 1
    j -= 1
    
    ans = max(ans, a*j)

print(ans)

ACとなるコード

from collections import defaultdict

k = int(input())
cnt = defaultdict(int)

s = k
i = 2
while i*i <= k and s != 1:
    while s%i == 0:
        cnt[i] += 1
        s //= i
    i += 1

if s != 1:
    cnt[s] += 1

ans = 1
for a, b in cnt.items():
    j = 1
    while b > 0:
        n = a * j
        while n%a == 0:
            n //= a
            b -= 1
        j += 1
    j -= 1
    
    ans = max(ans, a*j)

print(ans)

TLEのコードとACのコードの違い

20行目(下から10行)のところが

while b != 0:
while b > 0:

というだけです。

どうして、ここまで差が出るのかを教えてほしいです。

0

2Answer

while n%a == 0:のブロックが1ループあたり複数回実行されるのであれば、ループを抜けるタイミングでbは必ずしも0を経験せずマイナスの値になるのではないでしょうか?
while文は毎ループの最初に条件式の評価を行い、以降の処理を実行するかを決定します。

1Like

@Cartelet さんのおっしゃる通りです。
入力として4を与えたときに、どのような動きになるのか、ソースを追いかけてみることをお勧めします。
while b != 0:への到達時点での各変数の値が
1回目 : a=2, b=2, j=1
2回目 : a=2, b=1, j=2
3回目 : a=2, b=-1, j=3
4回目 : a=2, b=-2, j=4
5回目 : a=2, b=-5, j=5
...
となり、b != 0の条件が成立し続けて止まらないのが分かります。

1Like

Your answer might help someone💌