#45618: python不要TLE的做法


toitp (Toitp)

學校 : 不指定學校
編號 : 150438
來源 : [203.71.117.4]
最後登入時間 :
2025-03-25 14:14:00
e566. 10190 - Divide, But Not Quite Conquer! -- UVA | From: [203.71.117.4] | 發表日期 : 2025-03-24 14:51

你可以發現當 N 不是 M 的整數次方時,結果會是"Boring!"

然而連續乘法或連續除法都會帶來TLE

這時要用到log,如果「log N 以 M 為底」是整數的話,則輸出結果,反之則輸出"Boring!"

首先,import math

接著是判斷

  1. 如果 M < 2 要輸出"Boring!"
  2. math.log(N, M)是整數的話,輸出結果

判斷整數的方法可以這麼做:

if abs( math.log(N, M) - round(math.log(N, M)) ) < 0.0000001: return True

其中的 round(math.log(N, M)) 是取最接近該數的整數,

譬如math.log(1000, 10) = 2.9999999999999996,round的結果是3

又或者math.log(134217728, 8) = 9.000000000000002,round的結果是9
所以if abs( math.log(N, M) - round(math.log(N, M)) ) < 0.0000001 : return True 就是在判斷「如果兩數相差非常小,則代表他們一樣」的意思

以上

 
ZeroJudge Forum