如何優化一段代碼以在2秒內執行

Question

對於編程練習的挑戰，我編寫了這個python代碼，但給出了6秒的執行時間，但我希望它在2秒內執行。我應該如何修改這段代碼？未來的技巧也受到歡迎

times = int(raw_input()) 

for i in range (times): 
    count = 0 
    z = raw_input().split() 
    a,d = int(z[0]),int(z[1]) 
    p= int(raw_input()) 
    while a%p != 0: 
     a= a+d 
     count = count+1 
    print count 

簡介問題陳述的：

輸入格式：第一行包含一個數字，TC，表示測試用例的數量。第二行包含兩個整數，a和d - a描述了AP中的第一個術語，d描述了這個共同的區別。最後一行包含素數。

輸出格式：您必須打印給定AP中給定素數的倍數的第一個索引（從0開始）。如果此無限AP中不存在此元素，則打印-1。

限制條件：

0 <= a, d, <= 10^18 
1 <= p <= 10^9 

樣品輸入：

1 
4 9 
11 

樣本輸出：

2 

說明：AP將是：4,4 + 9 = 13，13+ 9 = 22,22 + 9 = 31 - 素數是11，所以索引是[2]。

Answer 1

您忘了將p%a更改爲a%p，這是您最後一次指出 您發佈了此問題。您還忘記了澄清真實數據需要六秒 秒，而不是此測試數據。

問題是您正在使用效率低下的蠻力算法。 嘗試extended Euclidean algorithm。